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: