1
$\begingroup$

Let $T$ be a (possibly improper) binary tree with $n$ nodes, and let $E(T)$ be the sum of the depths of all the external nodes of $T$. (In a proper binary tree each node have 0 or 2 children. An external node is a leaf, i.e., any node that is not an internal node.)

Is there a configuration for $T$ such that $E(T)$ is $\Omega(n^2)$? Is there an infinite sequence of trees $T_1,T_2,T_3,\dots$ such that $T_n$ has $n$ nodes and $E(T_n) = \Omega(n^2)$?


I have found 2 extreme cases for $E(T)$:

  • each internal node has 1 child (then $E(T)$ is $O(n)$), or

  • each internal node has 2 children (then $E(T)$ is $O(n \log_2 (n))$).

I have tried shaping the tree like this:

unbalanced tree

but as you can see it grows asymptoticly similar to Arithmetic Series and $E(T)$ is $O(n)$. I even showed it algebraically.


Internal nodes are just arithmetic sum, and leafs are the last term of this sum times 2.

$x$ - level of a tree $$\sum_{i=1}^{x}i=\frac{x(x+1)}{2}$$ $$\frac{x(x+1)}{2} + 2x = n$$ solving for x gives $$x = \sqrt{2n+\frac{25}{4}} - \frac{5}{2}$$
$x$ is $\Omega (\sqrt{n})$.
Now lets try calculation $E(T)$: There are $2x$ leafs each with depth $x$ $$E(T) = 2x \cdot x $$ $$E(T) \text{ is } \Omega (2\sqrt{n} \cdot \sqrt{n}) = \Omega(n) $$ So my question is how this tree should look like?

$\endgroup$
1
$\begingroup$

Consider a tree that has a chain of length $n/2$ at the top, where each node has exactly one child. Then, the remaining $n/2$ nodes are attached at the bottom of the chain, as a complete tree of depth $\log_2 (n/2)$.

With this shape, every leaf is at depth $n/2 + \log_2 (n/2) = \Theta(n)$. There are about $n/4=\Theta(n)$ leaves. So, the sum of the depths of the leaves is $E(T) = \Theta(n^2)$.

This is asymptotically optimal; no tree can have $E(T) = \omega(n^2)$, as the maximum possible depth is $n$, and the maximum number of leaves is $n$, so we have $E(T) \le n^2 = O(n^2)$.

$\endgroup$

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.