CS212 Exams
Spring 1999 - Final

Induction

The following struct definition define classes for binary trees:

(defstruct <tree>)

(defstruct (<leaf-node> <tree>))

(defstruct (<interior-node> <tree>)
  (left <tree>) (right <tree>))

Thus, a tree is either a leaf or else an interior node with left and right sub-trees. The height of a tree can be calculated as follows:

(defgeneric (height (t <tree>)))

(defmethod (height (t <leaf-node>)) 1)

(defmethod (height (t <interior-node>))
  (+ 1 (max (height (get-interior-node-left t))
            (height (get-interior-node-right t)))))

The number of interior nodes of a tree may be calculated as follows:

(defgeneric (interior-nodes (t <tree>))

(defmethod (interior-nodes (t <leaf-node>)) 0)

(defmethod (interior-nodes (t <interior-node>))
  (+ 1 (interior-nodes (get-interior-node-left t))
       (interior-nodes (get-interior-node-right t))))

Using induction, prove that if the the height of a tree is n, then t has at most 2^n-1-1 interior nodes. Be sure to (a) state formally the property you are to prove as a function of n, (b) state and prove the base case, (c) state your induction hypothesis, (d) state and prove the inductive case showing where you use your induction hypothesis. You do not need to use the substitution or environment models in your proof. The definitions of height and interior-nodes are given in code simply to clarify their definitions.

Solution

Return to CS 212 Final - Spring 1999