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