sum of heights in perfect binary tree

Question

the question:

what is the sum of heights of the vertices of a perfect binary tree (n vertices, the height of a leaf is 0)? explain shortly.

a. $\theta(logn) $ b. $\theta(nlogn) $ c. $\theta(n) $ d. $\theta(n^2) $

so, I know the answer is c, and I also saw a proof to this by searching in google. however, it was quite a long proof, and all I need is short explanation (that is a question from a test, and you have something like 5 minutes to answer it). I understood that there is a way of showing it by increasing and decreasing the sum of heights , but all I succeed in proving in this way is that the sum is O(nlogn).

how can you answer this shortly?

Answer 1

At height $1\leq i\leq \log n$, you have $2^{\log n -i -1} = 2^{-i}\frac{n}{2}$ vertices. Therefore, you want to compute $$ \sum_{i=0}^{\log n} i\cdot 2^{-i}\frac{n}{2} $$ It remains to show that $\sum_{i=0}^{\log n} i \cdot 2^{-i} = \Theta(1)$. The lower bound is easy, and the upper follows from $\sum_{i=0}^{\infty} i \cdot 2^{-i} = O(1)$.

Answer 2

Clearly, the sum of heights is $Ω(n)$. (About) half the nodes have height $0$, another quarter have height $1$ and so on. So you want $O{\left(n(\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\cdots) \right)}$. But that series is well known:

$\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\cdots$

$\ =(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots)$

$\quad\ + (\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\cdots)$

$\quad\ + (\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\cdots)$

$\quad\ \vdots$

which I am sure you can work out.

Answer 3

Call the sum of the heights $S(n)$. Now we have nice behaviour of $S(n)$ whenever $n = 2^k - 1$ i.e. for a full binary tree. In particular, the following recurrence relation holds:

$S(2^{k + 1} - 1) = S(2^{k} - 1) + (2^{k} - 1)$

Solving this with boundary condition $S(1) = S(2^1 - 1) = 0$, we get:

$S(2^k - 1) = 2^k - k - 1$

From here is is clear that the sum is proportional to the number of nodes: the $k$ term is swallowed by the exponential.

---

EDIT: Note for intermediate $n$ we have $2^k - 1 < n < 2^{k +1} - 1$ and $S(2^k - 1) < S(n) <= S(2^{k +1} - 1)$ so $2^k - k - 1 < S(n) <= 2^{k+1} - k - 2$

Answer 4

With $l$ complete levels, you have $n=2^l-1$ nodes. If you add a level, all the old nodes see their height increase by one, and the new ones ($n+1$ of them) have height $0$. This corresponds to the recurrence

$$S_{2n+1}=S_n+n,$$ or $$T_{l+1}=S_{2^{l+1}-1}=S_{2^l-1}+2^l-1=T_l+2^l-1.$$ As one can check, the solution is $$T_l=2^l-1-l,$$ $$S_n=n-\lg(n+1).$$

Incomplete levels yield the same sum as the complete ones, for the same tree height.