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:
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 2ドルx$ 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?
1 Answer 1
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)$.