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.

Answer 2

Let's assume at first that the tree is complete - it has 2^N leaf nodes. We try to prove that you need N recursive steps for a binary search.

With each recursion step you cut the number of candidate leaf nodes exactly by half (because our tree is complete). This means that after N halving operations there is exactly one candidate node left.

As each recursion step in our binary search algorithm corresponds to exactly one height level the height is exactly N.

Generalization to all balanced binary trees: If the tree has less nodes than 2^N we for sure don't need more halvings. We might need less or the same amount but never more.