CPSC 220 Fall 2005
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.  

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