CPSC 220 Fall 2006: Another Structural Induction Example

Base case: A binary tree with only one node has height 0 and has 1 leaf. 2⁰=1, so the property holds.

Inductive step: If any binary tree of height r, 0<=r<=k, has at most 2^r leaves, than any binary tree of height k+1 has at most 2^k+1 leaves.

Proof of inductive step: Consider a binary tree T of height k+1. Then there are two cases to consider:

   Case 1: T has only one subtree (T1). Since T is of height k+1, T1 must be of height k. By the inductive hypothesis, T1 has at most 2^k leaves. All of the leaves in T are in T1, so T also has at most 2^k leaves. 2^k < 2^k+1, so the property holds.

   Case 2: T has two subtrees (T1 and T2). Since T is of height k+1, at least one of T1 and T2 must be of height k. Call this subtree T1. By the inductive hypothesis, T1 has at most 2^k leaves. The other subtree, T2, could have any height h ranging from 0 to k. In any case the inductive hypothesis will apply, so if T2 is of height h then it has at most 2^h leaves. The largest possible value of h is k, so T2 has at most 2^k leaves. All of the leaves in T come from T1 and T2, so T has at most 2^k + 2^k = 2^k+1 leaves.