Proving Properties of Binary Trees -- Exercises

1. A full binary tree with n nodes has (n-1)/2 internal nodes and (n+1)/2 leaves.

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

2. Let E be the external path length of a tree, that is, the sum of the path lengths to all of the leaves. Let I be the internal path length, that is, the sum of the path lengths to all of the internal nodes. Let i be the internal nodes. Prove that in a proper binary tree, E=I+2i.

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

3. A proper binary tree always has an odd number of nodes.

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

4. Any tree with at least two nodes has at least two nodes of degree 1.