Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A complete binary tree is defined as a tree where each node has either 2 or 0 children.
For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the maximum depth of such a tree as $d$, it's clear that $d \ge \log_2n$.
The quantity I'm interested in is, the sum of depth of all leaves: $D$. What's the upper and lower bound of $D$ given $n$ and $d$?
When you construct such a tree and to add two more nodes as offspring to a leaf at depth $x$, what happens to $D$ is you subtract $x$ and add $2(x+1)$, therefore $D_{new} = D_{old} + x + 2$.
From this you can see that the best strategy to maximize $D$ is to always add nodes to the lowest node (furthest from root), therefore obtaining a tree that has one leaf on every level (except the 0th where the root is) and two leaves at the lowest level. The depth of this tree will be $(n+1)/2$ ($n$ is always odd for these trees). Therefore $$ D \le \frac{n+1}{2}-1+\sum_{i=1}^{\frac{n+1}{2}-1}i=\frac{n^2+4n-5}{8}$$ is your upper bound.
On the other hand if you want to minimize $D$ you want to always add children nodes to be closest to the root. Then your depth is $\log_2(n+1)$ (the last level is one less than depth) and you have again $(n-1)/2$ leaves. Therefore the lower bound is $$D \ge\frac{n-1}{2}\cdot\log_2(n+1)-1$$ for trees with $2^k -1$ nodes. For nodes with different number of leaves the bound still holds, but it won't be equal.
