Skip to main content
2 of 9
deleted 2 characters in body; edited title
Michael Albanese
  • 19.3k
  • 9
  • 87
  • 160

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))} \leq \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$.

Danny
  • 11
  • 2