1
$\begingroup$

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've proved the base case but I am struggling to figure out how to apply induction to prove for the $K+1$ case. Any suggestions would be wonderful.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ try to prove that any binary tree with $2^k$ nodes must have $k+1$ levels, it is better to avoid log. $\endgroup$
    – Denis
    Jun 11, 2013 at 16:21
  • 1
    $\begingroup$ and remember that a binary tree= 1 root+ 2 binary trees $\endgroup$
    – Denis
    Jun 11, 2013 at 16:23
  • $\begingroup$ Wonder if there is already a duplicate of this. $\endgroup$
    – Juho
    Jun 11, 2013 at 16:37
  • $\begingroup$ Raphael's answer of Proving a binary tree has at most $\lceil n/2 \rceil$ leaves should help for this question as well. $\endgroup$
    – FrankW
    May 9, 2014 at 10:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.