anyone explain thbis question??
Perfect binary tree quiz
Perfect binary tree question on trees quiz…
@shampblocks the answer is O(n) and can be proved by Induction, leaf nodes have zero height, now if root’s height is h, then number of nodes = 2^(h+1).
For h=0
sum=n-h-1. // you need not to know the exact relation we can get result with assumption of type an+bh +c, try do that on your own
Now assume for h=k its true
sum=2^k+1 -k -1
now for h=k+1
now we will need to add one to all non leaf nodes, non leaf nodes number= 2^h - 1= 2^k+1 -1
new sum= sum+ 2^k+1
2^(k+1) -k -1 + 2^(k+1 ) -1
simple rearrangement
2^(k+2) -(k+1) -1
2^(h+1) - (h)-1
n-h-1
so assumption is true.
Use pen and pencil do it on paper you will better understand this
If this resolves your doubt mark it as resolved.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.