Proving Properties of Binary Trees -- Exercises

Use induction to show each property below.
  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.