CPSC 220 Fall 2006: Structural Induction Example

Use structural induction to show that a nonempty proper binary tree (pbt) with N internal nodes has N+1 leaves. (Recall that a pbt is a binary tree in which every node has 0 or 2 children.)

Base case: A pbt with only one node has 0 internal nodes and 1 leaf, so the property holds.

Inductive step: If any nonempty pbt with r internal nodes, 0<=r<=k, has r+1 leaves, than any pbt with k+1 internal nodes has k+2 leaves.

Proof of inductive step: Consider a pbt T with k+1 internal nodes, k>=0. Then:

Since T is proper and has at least one internal node it must have two subtrees. Call them T1 and T2.
We don't know how many internal nodes T1 has, so just call that number p. Note that 0<=p<=k.
We know that T2 has all of the internal nodes in T except for those in T1 and the root of T, so T2 has k+1-p-1=k-p internal nodes.
By the inductive hypothesis, we know that T1 (which has p internal nodes) has p+1 leaves.
By the inductive hypothesis, we know that T2 (which has k-p internal nodes) has k-p+1 leaves.
All of the leaves in T are in either T1 or T2, so T has (p+1) + (k-p+1) = k+2 leaves. This is what we wanted to show for a tree with k+1 internal nodes.