For a perfect binary tree of height h and n nodes the sum of heights of all the nodes is:
O(h*h)
O(h)
O(n*n)
O(n)
what is the answer of this mcq and why?
Doubt in mcq question
hi @Akshita99, the answer should be O(n) ,
you can refer this discussion Perfect binary tree quiz
another way of this question is by observing the recurrence relation :-
in a perfect binary tree we have :-
height = log(n) (base 2)
n=2^(h+1)-1;
now if we know sum of heights for p.b.t of height h then let’s add another layer to our pbt making it of height h+1 and no of nodes added is (2^(h+1)) which is n+1
sum(h+1)=sum(h)+(2^(h+1))*(h+1)
since h is log(n)
so we get sum(h+1)-sum(h)=(n+1)(logn+1)
so by adding n+1 nodes we get increase in approx n nodes