## CPSC 220 Fall 2006: Another Structural Induction Example

Use structural induction to show that a nonempty binary tree of height N has at most 2N leaves.

Base case: A binary tree with only one node has height 0 and has 1 leaf. 20=1, so the property holds.

Inductive step: If any binary tree of height r, 0<=r<=k, has at most 2r leaves, than any binary tree of height k+1 has at most 2k+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 2k leaves. All of the leaves in T are in T1, so T also has at most 2k leaves. 2k < 2k+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 2k 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 2h leaves. The largest possible value of h is k, so T2 has at most 2k leaves. All of the leaves in T come from T1 and T2, so T has at most 2k + 2k = 2k+1 leaves.