2
$\begingroup$

I need to prove the following statement using induction on the number of nodes in the tree:

The sum of heights of a complete binary tree is $\theta(n)$.

Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)≤c_1n$ for some $c_1$. But, I couldn't show the lower bound ($sum(n)≥c_2n$ for some $c_2$).

The base case is a complete binary tree, with 3 nodes in the height of 1.

The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$

I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree.

Can someone explain how to complete this step?

$\endgroup$
1
$\begingroup$

A complete binary tree of height $h$ has exactly $2^{h-k}$ nodes of height $k$ for $k=0,\ldots,h$, and $n=2^0+\cdots+2^h = 2^{h+1}-1$ nodes in total. The total sum of heights is thus $$ \sum_{k=0}^h 2^{h-k}k = 2^h \sum_{k=0}^h \frac{k}{2^k} = 2^h \left(2 - \frac{h+2}{2^h}\right) = 2^{h+1} - (h+2) = n - \log_2 (n+1). $$


The answer below refers to full binary trees.

I'm assuming the following definition of height. The height of a tree is the length of the longest root-to-leaf path. The height of a vertex in a tree is the height of the subtree rooted at this vertex. Denote the height of a tree $T$ by $h(T)$ and the sum of all heights by $S(T)$.

Here are two proofs for the lower bound. The first proof is by induction on $n$. We prove that for all $n \geq 3$, the sum of heights is at least $n/3$. The base case is clear since there is only one complete binary tree on $3$ vertices, and the sum of heights is $1$. Now take a tree $T$ with $n$ leaves, and consider the two subtrees $T_1,T_2$ rooted at the children of the root, containing $n_1,n_2$ vertices, respectively. Suppose first that $n_1,n_2 \geq 3$. Then $$ S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + n_1/3 + n_2/3 = n/3 + 2/3 > n/3. $$ If (say) $n_2 = 1$ then $$ S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + (n-2)/3 = n/3 + 1/3 > n/3. $$ This completes the proof.

The second proof proceeds by bounding the number of leaves in a complete binary tree. Order the children of every node so that it has a left child and a right child. Exactly half of the leaves are left children. Each left child has a different parent, and in particular each left leaf has a different parent. So a tree $T$ with $f$ leaves has at least $f/2$ non-leaves. In particular, the total number of vertices $n$ satisfies $n \geq f + f/2 = (3/2)f$, so that $(2/3)n \geq f$ and so $n-f \geq n/3$. We conclude that $S(T) \geq n-f \geq n/3$.

The upper bound can be proved along the lines of the second proof. Suppose that there are $f$ leaves. Thus there are at most $f/2$ vertices at height $1$, at most $f/4$ vertices at height $2$, and generally speaking, at most $f/2^h$ vertices at height $h$. Therefore the total height of vertices is at most $$ \sum_{h=0}^\infty h \frac{f}{2^h} = f \sum_{h=0}^\infty \frac{h}{2^h} = 2f \leq 2n. $$

$\endgroup$
  • $\begingroup$ Thank you for helping me out. I have one question though. How did you reach to $n/3$? Why exactly $1/3$? Is it possible to write $c_1$ instead of a particular number? $\endgroup$ – Alexs68 Nov 19 '15 at 16:34
  • $\begingroup$ The bound $1/3$ is tight, since when $n=3$ the sum of heights is $1$. For $n \geq 5$, the sum of heights depends on the tree, so you can't expect the constants $c_1$ and $c_2$ to be the same even if you fix $n$. $\endgroup$ – Yuval Filmus Nov 19 '15 at 16:36
  • $\begingroup$ I might have misunderstood your question - my answer works for full rather than complete binary trees. (Full binary trees are ones in which each node has either no or two children.) Since complete binary trees are full, my answer is also good for you, but for complete binary trees you can get much better bounds. See my edited answer. $\endgroup$ – Yuval Filmus Nov 19 '15 at 17:12
  • $\begingroup$ You have justification for misunderstanding the question. Just out of curiosity I looked at some of the "standard" CS texts and discovered, as I expected, several conflicting definitions of "complete" and "full" binary trees. In this area, it behooves an author to provide definitions of what the terms mean. $\endgroup$ – Rick Decker Nov 19 '15 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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