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?