Recap definition of rank and the claim, for reference. (You don't have to include these as part of your solution.)
If T is a binary tree with root r, then its rank is
- 0 if r has no children
- 1+q if r has two children, both with rank q
- otherwise, the maximum rank of any of the children
Claim: a tree with rank q has at least \(2^q\) leaves
Let's use the notation rank(T) for the rank of a tree T.
Proof by induction on h, which is the height of the tree.
Base: h=0. In this case, the tree has only one node. Its rank is zero. And it has \(2^0 = 1\) leaves. So the claim is true for h=0.
Inductive hypothesis: Suppose that trees with rank q have at least \(2^q\), for trees of height \(h=0,1,\ldots,k-1\), where \(k \ge 1\).
Rest of inductive step: Let T be a tree of height k.
There are two cases:
Case 1: T has one child subtree. Let's call it \(T_1\). Suppose that \(\text{rank}(T_1) = q\). Then \(\text{rank}(T) = q\) by the definition of rank.
Since \(T_1\) has height less than k, the inductive hypothesis tells us that \(T_1\) has at least \(2^q\) leaves. But all the leaves of \(T_1\) are also leaves of T. So T also has at least \(2^q\) leaves.
Case 2: T has two child subtrees. Let's call the left subtree \(T_L\) and the right subtree \(T_R\). There are three subcases:
Case 2a: \(\text{rank}(T_L) > \text{rank}(T_R)\). Let's set \(q = \text{rank}(T_L)\). Then \(\text{rank}(T) = q\) by the definition of rank.
Since \(T_L\) has height less than k, the inductive hypothesis tells us that \(T_L\) has at least \(2^q\) leaves. But all the leaves of \(T_L\) are also leaves of T. So T also has at least \(2^q\) leaves.
Case 2b: \(\text{rank}(T_R) > \text{rank}(T_L)\). Similar to Case 2a.
Case 2c: \(\text{rank}(T_R) = \text{rank}(T_L)\). Let's set r to be this shared rank. Then \(\text{rank}(T) = r + 1\) by the definition of rank.
Since \(T_L\) and \(T_R\) both have height less than k, the inductive hypothesis tells us that each of them has at least \(2^r\) leaves. The number of leaves in T is the sum of the number of leaves in \(T_L\) and \(T_R\). This is \(2^r + 2^r = 2^{r+1}\) leaves. So T has rank r+1 and has at least \(2^{r+1}\) leaves.
In all four cases T has at least \(2^{q}\) leaves, where q is the rank of T. This is what we needed to prove.
Notice that we defined a new piece of notation "rank(T)". Defining new notation can be very useful for keeping your proof easy to write. If you do this, make sure to tell the reader what the notation means, before you start using it.
The above proof has four separate (sub)cases. This is a very safe strategy. And it's always a very good idea to write out such cases separately on your scratch paper, so it's easy to make sure you've covered all the possibilities. If you are a good writer, you might be able to combine some of the cases in the final draft. For example, you might use "without loss of generality" to combine 2a and 2b.
Case 2b is not just similar to case 2a. It's almost identical. So it's very safe to omit the details of 2b.