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
Proof of inductive step: Consider a pbt T with k+1 internal nodes,
- 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
- 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.