Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ How does showing that $8\geq 3$ establish anything about binary trees? You need to relate the number of leaves and numebr of levels, not $n$ and $\log n$. $\endgroup$– David RicherbySep 21, 2014 at 23:56
-
3$\begingroup$ What does the shallowest binary tree on $n$ nodes look like? There will be 1 node at the root (level 0), 2 child nodes at level 1, 4 at level 2 so for $n = 7 (=1+2+4)$ there must be at least 2 levels. Generalize this. $\endgroup$– Rick DeckerSep 22, 2014 at 0:56
-
$\begingroup$ Related question. $\endgroup$– d'alar'copSep 22, 2014 at 4:04
-
$\begingroup$ The induction is elementary; do you understand induction in principle? What has to be the anchor here? Over which quantity should we do the induction? $\endgroup$– Raphael ♦Sep 22, 2014 at 6:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.
answered Sep 22, 2014 at 2:14