1
$\begingroup$

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.

$\endgroup$
  • 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 Richerby Sep 21 '14 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 Decker Sep 22 '14 at 0:56
  • $\begingroup$ Related question. $\endgroup$ – d'alar'cop Sep 22 '14 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 '14 at 6:35
1
$\begingroup$

Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.

$\endgroup$

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.