Solution to Homework #4

17.3) a b b d d d b a c e e e c c a

17.5) Let S be the maximum number of nodes in a tree of height H,
      	      S = 2^0 + 2^1 + ... + 2^H   --------(1)
      2*(1)-> 
              2S =      2^1 + 2^2 + ... + 2^(H+1) -------(2)
      (2) - (1) ->
              2S - S = 2^(H+1) - 1
                   S = 2^(H+1) - 1         Q.E.D

17.6) Prove that the number of leaves = the number of full nodes plus 1.

      We prove it by induction on the number of full nodes.
      Base case: Single-node tree -> 1 leaf, 0 full node.
                 Tree with one full node -> 2 leaves, 1 full node.

      Inductive case: Assume that all binary trees with n full nodes have 
                      n + 1 leaves.
      We need to show that a tree with n+1 full nodes has n + 2 leaves:
      A tree with n+1 full nodes can be formed from a tree with n full 
      nodes in 3 ways:

      1) Make a non full nodes a full node by adding one leaf node.

      2) Add 2 children to a leaf node.

      3) Place a n-full node tree as another child of an unfull 
	 parent with one leaf node. 

     From those 3 method, the number of full nodes is increased by 
     one and the number of leaves is also increased by one.