Maximum sum of depths of all external nodes in a Binary Tree - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:12:34Z https://cs.stackexchange.com/feeds/question/87336 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/87336 1 Maximum sum of depths of all external nodes in a Binary Tree Bobi https://cs.stackexchange.com/users/83345 2018-01-25T23:26:37Z 2018-01-26T21:44:22Z <p>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.)</p> <p>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)$?</p> <hr> <p>I have found 2 extreme cases for $E(T)$: </p> <ul> <li><p>each internal node has 1 child (then $E(T)$ is $O(n)$), or</p></li> <li><p>each internal node has 2 children (then $E(T)$ is $O(n \log_2 (n))$).</p></li> </ul> <p>I have tried shaping the tree like this:</p> <p><a href="https://i.stack.imgur.com/HwNeU.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HwNeU.png" alt="unbalanced tree"></a> </p> <p>but as you can see it grows asymptoticly similar to Arithmetic Series and $E(T)$ is $O(n)$. I even showed it algebraically. </p> <hr> <p>Internal nodes are just arithmetic sum, and leafs are the last term of this sum times 2. </p> <p>$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}$$<br> $x$ is $\Omega (\sqrt{n})$.<br> 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?</p> https://cs.stackexchange.com/questions/87336/-/87377#87377 1 Answer by D.W. for Maximum sum of depths of all external nodes in a Binary Tree D.W. https://cs.stackexchange.com/users/755 2018-01-26T21:44:22Z 2018-01-26T21:44:22Z <p>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)$.</p> <p>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)$.</p> <p>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)$.</p>