## CPSC 220 Fall 2005

HW 9: More Binary Tree Proofs

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

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