Ratio between number of nodes and leaves in a rooted binary tree

Question

I want to know if there exists a positive constant $c$ such that: Given rooted binary tree, $T$, with root $r$ and height $h$ (not necessarily a full tree), the following holds:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T(r))}{ N(T(r))} \geq c\sqrt{2^h}$$

where $T(v)$ is the sub-tree of $T$ rooted at $v$ (so for example, $T(r) = T$), $N(T(r))$ is the number of nodes in said tree, $L(T(v))$ is the number of leaves in the said tree and $h(v)$ is $v$'s height in $T$. Furthermore the sum is taken over all nodes, $v$, that aren't leaves of $T$.

So for example, if $T$ was the full binary tree we'd get the ratio:

$\frac{2^h + 2*2^h + 4*2^h + \dots + 2^{h-1}*2^h + 2^h}{1 + 2 + \cdots + 2^h} = \frac{2^{2h}}{2^{h+1} - 1}$ which is indeed greater than $2^{h/2}$ (for $h \geq 2$).

Answer 1

We can prove a lower bound on the expression by considering only vertices immediately below a leaf:

$$\frac{[\sum_{v \in T \text{ not a leaf}}2^{h(v)}L(T(v))] + L(T)}{N(T)} \geq \frac{[\sum_{v \text{ below a leaf}}2^{h(v)}L(T(v))] + L(T)}{N(T)}.$$

For each such $v$, $L(T(v)) \geq 2$ and there are at most two leaves immediately above $v$, so

$$\frac{[\sum_{v \text{ below a leaf}}2^{h(v)}\cdot L(T(v))] + L(T)}{N(T)} \geq \frac{\frac{1}{2}[\sum_{v \text{ a leaf}}2^{h(v)-1}\cdot 2] + L(T)}{N(T)}.$$

Now $N(T) = 2L(T) - 1$, so we are working with an expression that is approximately

$$\frac{1}{4L(T)}\sum_{v \text{ a leaf}}2^{h(v)}.$$

This is (a quarter of) the average value for $2^{h(v)}$ when $v$ is a leaf. To decrease the value without changing the height, one could attach a "V" on the top of some leaf $v'$ for which $3\cdot 2^{h(v')}$ is below the average. One could also remove a "V" with two leaves that produce an above-average value, so long as at least one leaf of height $h$ remains.

So the minimum average for some fixed height $h$ will be obtained by a tree that is (approximately) a full binary tree of height $h'$ with a single branch growing up to height $h$. Then

\begin{eqnarray} \frac{1}{4L(T)}\sum_{v \text{ a leaf}}2^{h(v)} & \approx & \frac{1}{4(h - h' + 2^{h'})} \left[\left(\sum_{i = h'}^{h} 2^i\right) + \left(2^{h'}\right)^2 \right]\\ &\geq& \frac{1}{4}\frac{1}{(h - h' + 2^{h'})} \left[2^h + 2^{2h'}\right]\\ & \geq & \frac{1}{4}2^{h/2} \end{eqnarray} for all sufficiently large $h$ and all $h' < h$. Indeed, for small $h'$, $\frac{1}{h}2^{h}$ dominates; if $h'$ is large enough for $2^{h'}$ to dominate the denominator and $\frac{1}{2^{h'}}2^h < 2^{h/2}$, then $h' > h/2$ and $\frac{1}{2^{h'}}2^{2h'} > 2^{h/2}$.