##
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.