I have a full binary tree with $n$ leaf nodes. Therefore we get the following constraint $\sum_{i=1}^{n}2^{-l_{i}} = 1$ where $l_i$ is the level occupied by each leaf node.
I have the metric $\frac{1}{n}\sum_{i=1}^{n}2^{l_{i}}$.
What I would like to show is, that the more unbalanced the tree is, the higher the metric. Since there is no universal metric for tree unbalance-ness, I dont know how to go about it.
Possible Directions -
- I tried to show that an act of unbalancing a tree increases the metric.
- I can show that the metric is lower bounded by $n$ using the AM-HM inequality.
Let $\ell_1$ be the minimum depth of a leaf and $\ell_n$ the maximum depth; since the tree is full, there must be a sibling pair of leaves at depth $\ell_n$. If $\ell_n\ge\ell_1+2$, remove a sibling pair at depth $\ell_n$, and give a leaf at depth $\ell_1$ a pair of children; this loses two leaves at depth $\ell_n$, adds one at depth $\ell_n-1$, adds two at depth $\ell_1+1$, and loses one at depth $\ell_1$, for a net change in $\sum_{k=1}^n2^{\ell_k}$ of
$$2^{\ell_n-1}-2\cdot 2^{\ell_n}+2\cdot 2^{\ell_1+1}-2^{\ell_1}=3\left(2^{\ell_1}-2^{\ell_n-1}\right)<0\,.$$
(I ignore the factor of $\frac1n$, since $n$ is not changed by this procedure.) Thus, as long as the tree is not balanced, this procedure will reduce your metric.