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
  • 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$ Commented Sep 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$ Commented Sep 22, 2014 at 0:56
  • $\begingroup$ Related question. $\endgroup$
    – d'alar'cop
    Commented Sep 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
    Commented Sep 22, 2014 at 6:35

1 Answer 1

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 and acknowledge you have read our privacy policy.

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