CPSC 220 Fall 2005
HW 9: More Binary Tree Proofs

  1. Finish the fill-in-the-blank path length proof from class.

  2. Use a similar inductive proof to show that the number of leaves in any binary tree (not necessarily proper) is one more than the number of nodes with two children. Hint: You will need to consider separately the case where the root has one subtree and the case where the root has two subtrees.