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.

  • 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
    Commented Jun 11, 2013 at 16:21
  • 1
    $\begingroup$ and remember that a binary tree= 1 root+ 2 binary trees $\endgroup$
    – Denis
    Commented Jun 11, 2013 at 16:23
  • $\begingroup$ Wonder if there is already a duplicate of this. $\endgroup$
    – Juho
    Commented 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
    Commented May 9, 2014 at 10:36


Your Answer

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