Answers to G5BADS 2004-5 informal coursework 2

G5BADS 2004-5 informal coursework 2

Prove by mathematical induction that a proper binary tree with k levels contains 2^k-1 leaves.
Proof:
Basis of induction (k = 1): a perfectly balanced tree with one level (just the root) has one leaf (one node with no children). 1 = 2⁰ = 2^{1 - 1} so the claim is correct for k = 1.
Inductive step : if the claim is true for proper binary trees with n levels, it is true for proper binary trees with n+1 levels.
Assume that in a proper binary tree with n levels there are 2^n-1 leaves. A perfectly balanced tree with n+1 levels has twice more leaves (since every node on level n-1, which is a leaf in a tree with n levels, now has two children which are leaves in a tree with n+1 levels). So a proper binary tree with n+1 levels has 2 * 2^n-1 = 2ⁿ leaves, which is the same as 2^(n+1)-1 leaves. If the claim holds for a tree with n levels, it holds for a tree with n+1 levels.