CPSC 220 Fall 2005HW 8: Proving Properties of Binary Trees

In class we did an inductive proof to show that a full binary tree with n nodes has (n+1)/2 leaves. It looked something like this:

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.

Assignment

1. 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.

2. 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 2k 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.)
1. 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!

2. 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)