Prove that the average height of a full binary tree is greater or equal to the logarithm of its leaf count

Question

The average height of a full binary leaf (a node is either a parent with 2 childs or a leaf) is:

$$h_m(T) = \frac{1}{|B(T)|}\sum_{b\in B(T)}\operatorname{depth}(b)$$

B(T) is the set of leaves. Now I wanna prove that $h_m(T)\geq \log_2(|B(T)|)$ is true. I was given a few hints:

1. First prove that $h_m(T)\geq \frac{|B(T_1)|\log(B(T_1)+|B(T_2)|\log(B(T_2)}{|B(T)|}+1$ is true.
2. Determine the minimum of $|B(T_1)|\log(B(T_1)+|B(T_2)|\log(B(T_2)$ analyzing the function $f_{\alpha}(x)=x\log(x)+(\alpha-x)\log(\alpha-x)$ where $|B(T)|=\alpha$ --> already find out that this function is minimal for $\frac{\alpha}{2}$.
3. Now show that the assumption above is true.

Answer 1

I will use the notation $V(G)$ for the vertex set of a graph, $G$, and I will subscript $\operatorname{depth}_T$ for a leaf of the rooted tree, $T$, since it adds to clarity.

Since a full rooted binary tree with $\lvert V(T)\rvert = 1$ has $1$ leaf and an average leaf depth of $0$, we have $h_\text{avg}(T) = \log_2\lvert B(T)\rvert$ for this case.

We can proceed by strong induction, assuming that $h_\text{avg}(T) \geq \log_2\lvert B(T)\rvert$ whenever $T$ is a full rooted binary tree with $\lvert V(T)\rvert\leq n$ for some fixed $n\geq 1$.

If $T$ is a full rooted binary tree with $\lvert V(T)\rvert = n + 1$, then the two children of the root of $T$ are the roots of subtrees called $T_1$ and $T_2$. Every leaf of $T$ is a leaf of $T_1$ or of $T_2$, and the two sets of leaves are disjoint. Since $\lvert V(T_i)\rvert\leq n$ for these two subtrees, we apply the inductive hypothesis to get

$$\begin{align*} \sum_{b\in B(T)} \operatorname{depth}_T(b) &= \sum_{b\in B(T_1)}\operatorname{depth}_T(b) + \sum_{b\in B(T_2)}\operatorname{depth}_T(b) \\ &= \sum_{b\in B(T_1)}\big(1 + \operatorname{depth}_{T_1}(b)\big) + \sum_{b\in B(T_2)}\big(1 + \operatorname{depth}_{T_2}(b)\big) \\ &= \lvert B(T_1)\rvert + \sum_{b\in B(T_1)}\operatorname{depth}_{T_1}(b) + \lvert B(T_2)\rvert + \sum_{b\in B(T_2)}\operatorname{depth}_{T_2}(b) \\ &= \lvert B(T)\rvert + \sum_{b\in B(T_1)}\operatorname{depth}_{T_1}(b) + \sum_{b\in B(T_2)}\operatorname{depth}_{T_2}(b) \\ &\geq \lvert B(T)\rvert + \lvert B(T_1)\rvert\log_2\lvert B(T_1)\rvert + \lvert B(T_2)\rvert\log_2\lvert B(T_2)\rvert. \end{align*}$$

If we divide through by $\lvert B(T)\rvert$, we get the inequality in your first given hint.

Since you’ve already done the work to show that $\lvert B(T_1)\rvert\log_2\lvert B(T_1)\rvert + \lvert B(T_2)\rvert\log_2\lvert B(T_2)\rvert$ is minimized when $$\lvert B(T_1)\rvert = \lvert B(T_2)\rvert = \frac{\lvert B(T)\rvert}{2},$$

you should be able to substitute these values for $\lvert B(T_1)\rvert$ and $\lvert B(T_2)\rvert$ into the inequality to arrive at the desired conclusion for the inductive step.