Question

The height of a binary tree having 'i' nodes at level 'i' considering root to be at level 1 is ------. where 'n' is the total no of nodes in the tree.

A. O(logn)

B. O(n)

C. O(ROOT(N))

D. O(N2)

Answer 1

No of nodes =n

N = summation of n from i=1to h

N= n² from 1to h

N= h² -1

√N+1= h

h=O(√N)

Answer 2

Let's assume height of the binary tree is h. Then,
n = 1 + 2 + 3 + ... + h = h(h+1)/2
h2 + h - 2n = 0
h = (−1 ± √(1 + 8n))/2 = O(√n)

ref: http://www.techtud.com/doubt/height-binary-tree-having-i-nodes-level-i-co