HW 8: Proving Properties of Binary Trees

Base case:A tree containing only 1 node is full and has (1+1)/2=1 leaves.Inductive step:If a full binary tree with 1<=r<=k nodes has (r+1)/2 leaves, then a full binary tree with k+1 nodes has (k+2)/2 leaves.Proof:Consider a full binary tree T with k+1 nodes, k>=1.

- Since T is full and has more than one node, it consists of a root
plus two subtrees, each of which is also a full binary tree. Call
the left subtree T1 and the right subtree T2.
- T1 and T2 are both full binary trees of the same height (since T
is full), so they must have the same number of nodes. T has k+1 nodes, the
root plus the nodes in T1 and T2. So T1 and T2 must each have k/2 nodes.
- By the inductive hypothesis, T1 and T2 each contain (k/2 + 1)/2 leaves.
- Since all of the leaves in T are in either T1 or T2, T must contain 2*((k/2 + 1)/2) = (k/2 + 1) = (k+2)/2 leaves.

- Use a similar inductive proof to show that a full binary
tree with n internal nodes has n+1 leaves. (Yes, this is basically
the same property, but prove it from scratch.) Do this on a separate sheet.
- In class (as above) we proved that a full binary tree with
n nodes
has (n+1)/2 leaves. Is this property also true for a proper binary tree?
(Remember that a proper binary tree is
one in which every node has 0 or 2 children but level k may not
have 2
^{k}nodes -- that is, it may not be completely filled in. Note that every full binary tree is proper, but not every proper binary tree is full.)- In the space below, draw a few proper (but not full)
binary trees, determine the number of nodes and leaves for each,
and convince yourself that the property holds.
**This is important to get intuition for what you are doing!**

- Fill in the blanks in the proof below to prove it. Note that the
strategy has to change a little from what we did with the full binary
tree.
Show that a proper binary tree with n nodes has (n+1)/2 leaves.

__Base case:__A tree containing only 1 node is proper and has (1+1)/2=1 leaves.__Inductive step:__If a proper binary tree with _____________ nodes has __________ leaves, then a proper binary tree with _____________ nodes has ______________ leaves.__Proof:__Consider a proper binary tree T with k+1 nodes, k>=1.- Since T is proper and has more than one node, it consists
of a root plus two subtrees, each of which is also a
proper binary tree. Call the left subtree T1 and the
right subtree T2.
- T1 and T2 are both proper, but they do not need to have
the same number of nodes. Suppose that T1 has x nodes,
x>=1. Then T2 must have ____________ nodes. (Hint: All the
nodes in the tree except the root and those in T1.)
- By the inductive hypothesis, T1 must have ______________
leaves and T2 must have _________________ leaves.
- Since all of the leaves in T are in either T1 or T2, T must contain __________________ + ____________________ =_________________________________________________________ leaves.(Show simplification)

- Since T is proper and has more than one node, it consists
of a root plus two subtrees, each of which is also a
proper binary tree. Call the left subtree T1 and the
right subtree T2.

- In the space below, draw a few proper (but not full)
binary trees, determine the number of nodes and leaves for each,
and convince yourself that the property holds.