##
CPSC 220 Fall 2006: Another Structural Induction Example

**Use structural induction to show that a nonempty
binary tree of height N has at most 2**^{N} leaves.
__Base case:__ A binary tree with only one node has height 0 and has
1 leaf. 2^{0}=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.