Binary Tree Height

Question

I need a general formula to calculate the minimum height of the binary tree and the maximum height of the binary tree. (not the binary search tree)

Answer 1

If you have N elements, the minimum height of a binary tree will be log2(N)+1.

For a full binary tree, the maximum height will be N/2.

For a non-full binary tree, the maximum height will be N.

Answer 2

N - number of nodes.
H - height of the binary tree.

Complete Binary Tree:
Then, with H height N would lie between:

2^H <= N <= (2^(H+1) - 1)

Thus, solving this inequality; we get :

H <= lg(N)  and  H >= (lg(N+1) - 1)

Hence we finally get:

H = floor( lg(N) ) = ceil( (lg(N+1) - 1) )   //as H is integer

(lg : log base 2)

Binary Tree (not necessarily complete):

Max height = N;  

Min Height = floor( lg(N) ) = ceil( (lg(N+1) - 1) )

We get minimum height when binary tree is complete.