Maximum sum of depths of all external nodes in a Binary Tree

Question

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 $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?

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