Skip to main content
4 of 9
added 1 character in body
Danny
  • 11
  • 2

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

I want to know if exists a constant $c$ such that: Given a rooted binary tree (not necessarily a full one), $T$, with root $r$ and height $h$ (a single node has height 0) 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 a 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 large enough $h$ that is).

Thanks :)

Danny
  • 11
  • 2