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$).

  • $\begingroup$ I removed what seemed like unnecessary brackets. Feel free to put them back in if you wanted them for some particular reason. $\endgroup$ Aug 10 '16 at 14:31
  • $\begingroup$ The inequality was the wrong way and a bracket was missing - fixed both. $\endgroup$
    – Danny
    Aug 10 '16 at 14:34

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}$.

  • $\begingroup$ I suspect that, when all non-leaf nodes are considered, a lower bound of $2^{h(1-\epsilon)}$ is possible for fixed $\epsilon >0$ and all sufficiently large $h$. Both the full binary tree and the skinniest binary tree of height $h$ attain this. $\endgroup$
    – D. Ror.
    Oct 4 '16 at 22:17
  • $\begingroup$ Because of the approximations in this solution some $c > \frac{1}{4}$ may be necessary. $\endgroup$
    – D. Ror.
    Oct 5 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.