Proof that the height of a balanced binary-search tree is log(n)

Question

The binary-search algorithm takes log(n) time, because of the fact that the height of the tree (with n nodes) would be log(n).

How would you prove this?

Answer 1

Now here I am not giving mathematical proof. Try to understand the problem using log to the base 2. Log₂ is the normal meaning of log in computer science.

First, understand it is binary logarithm (log₂n) (logarithm to the base 2). For example,

• the binary logarithm of 1 is 0
• the binary logarithm of 2 is 1
• the binary logarithm of 3 is 1
• the binary logarithm of 4 is 2
• the binary logarithm of 5, 6, 7 is 2
• the binary logarithm of 8-15 is 3
• the binary logarithm of 16-31 is 4 and so on.

For each height the number of nodes in a fully balanced tree are

    Height  Nodes  Log calculation
      0        1      log21 = 0
      1        3      log23 = 1
      2        7      log27 = 2
      3       15      log215 = 3

Consider a balanced tree with between 8 and 15 nodes (any number, let's say 10). It is always going to be height 3 because log₂ of any number from 8 to 15 is 3.

In a balanced binary tree the size of the problem to be solved is halved with every iteration. Thus roughly log₂n iterations are needed to obtain a problem of size 1.

I hope this helps.