Solution to Induction

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

1. Induction is over the depth of the tree, depth(t)
2. Assume that for any tree s of depth m <= d that (count-leaves s) counts the number of leaf nodes in s [Induction Hypothesis]
3.  

Base Case: depth(t) = 0, i.e., t is a leaf

(count-leaves t)
(if (leaf? t) 1 ...)

which is 1 because t is a leaf, as stated above.

Induction:
Assume t is a tree of depth d+1 and that for any tree s of depth <= d that (count-leaves s) is the number of leaves in s.

(count-leaves t)

(if (leaf? t) 1 (+ (count-leaves (get-tree-left t)) (count-leaves
(get-tree-right t))))

(+ (count-leaves (get-tree-left t)) (count-leaves (get-tree-right t)))

by substitution, because t cannot be a leaf (d+1 is strictly greater than 1).

We also know that (get-tree-left t) and (get-tree-right t) are of depth at most d-1 by the definition of trees. Thus by the induction hypothesis, the sum (+ (count-leaves (get-tree-left t)) (count-leaves (get-tree-right t))) is the total number of leaves in t.

Question

Return to CS 212 Prelim 1 - Fall 1996