Question

Use induction,

Prove that the height of the balanced BST is bounded by log(n).

Answer 1

Let us take the height of the binary tree is h.

Now, for the root level the number of nodes present is only the root node. So roots present is 1. (Level 0)

On the very next level down the roots the number of nodes present in a complete balanced BST is 2. (level 1)

Again for the next level no of nodes has to be 4. (level 2)

................

................

...............

...............

And the height being h, the number of nodes in the h^th level = 2^h

So now the total number of nodes present = 1+2+4+......+2^h

=2⁰+2¹+2²+....+2^h

=2^(h+1) - 1

So now if we consider that there are n nodes in the balanced binary tree, then,

n = 2^(h+1) - 1

or, n+1 = 2^(h+1)

or, (n+1)/2 = 2^h

or, h = log{(n+1)/2}

so, here we see that the height h is bounded by O(log(n)).