0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.