Tree problem 1

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

Solution to part (c)

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.