Question

How many levels will there be in a complete binary tree is it has n number of nodes?

looking for formula

Answer 1

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Suppose height of tree = h. then #levels (L) = h+1 .

then maximum possible nodes in complete binary tree is when all levels are completely filled means

at rpot level i.e. level 1 #nodes = 1 = 2^0

at level 2 #nodes = 2=2^1

at level 3 #nodes = 4=2^2

at level 4 #nodes = 8=2^3

at level 5 #nodes =16= 2^4

.

.

.

.

.

at level h #nodes = 2^(h-1)

at level h+1 #nodes = 2^h

total = 2^0 + 2^1 + 2^2 + 2^3 + ………+2^(h-1) + 2^h

====> 1+2+4+8+…………………………………….+2^h

so given number of nodes in complete binary tree must be at most = total

i.e. n<= total

n<= 1+2+4+8+…………………………………….+2^h

n<= 2^(h+1)

n<= 2^L (becoz, L= h+1)

log2(n) <=L

L >= log2(n)

L = ceil ( log2(n) )