Lesson Plan

Lesson title

Lesson Description

This lesson describes binary trees. A separate lesson plan will be used to teach Binary Search Trees (BST).

Prerequisite Knowledge

Length of Completion

90 minutes.

Level of Instruction

This lesson is for High School Juniors and Seniors.

Concepts to be Taught

1. Basics of Binary Trees

2. Definitions of Trees

3. Basic Formulae for Binary Trees

4. How to Parse:

• Preorder

• Postorder

• Inorder

• Level Order

Resources Needed

CodeSchool YouTube Video: https://www.youtube.com/watch?v=H5JubkIy_p8

Accommodations

Lesson Outcomes (TSWBAT ...)

Interconnection with Other Lessons

Assessments

Extension Activities

Differentiated Learning Opportunities

Lesson Warm Up

Describe how the Java Set interface derives two concrete classes, HashSet and TreeSet. Describe how the Java Map interface derives two concrete classes, HashMap and TreeMap. Mention that our study of trees will help students understand the internal structures of TreeSets and TreeMaps. We will learn about HashSets and HashMaps later in the year when we discuss Hashing.

Lesson Details for Binary Tree

1. Each node can have at most two children - left child and right child

2. Nodes with no children are leaf nodes. Nodes with children are internal nodes.

3. When a child is not present, the corresponding pointer is set to null.

4. Ask if a Linked List is an example of a binary tree. (It is).

5. Binary Tree Definitions:

   • Trees for which all nodes have exactly zero or two children are called Strict, Proper or Full Binary Trees.

   • Complete Binary Trees are binary trees for which all levels (except possibly the last level) are completely filled. The last level can be partially filled. But any existing nodes must be as far left as possible. Mention importance of Complete Binary Trees for heaps.

   • Review concepts of level, depth and height. Levels start numbering at zero.

   • Note the two possible definitions of height of a tree.

   • Max number of nodes at Level i = 2^i

   • A Perfect Binary Tree all levels are filled.

   • If a height of a perfect binary tree (h) will have 2^(h+1) - 1 = 2^0 + 2^1 + ... + 2^h

   • What will be the height of a complete binary tree with n nodes?

h = log2(n+1) -1 or floor(log2(n))

• These formulae will be useful when we calculate the efficiency (Big O) of various tree operations.

• A binary tree will have max height (n-1) when a tree degenerates to a Linked List.

• We want to keep a binary tree balanced. We want to keep the heights of left and right subtree not differ by more than 1.