in DS recategorized by
198 views
0 votes
0 votes

Someone please explain the login behind the explanation.

in DS recategorized by
198 views

1 Answer

1 vote
1 vote

Number of different max heap possible using n distinct keys is given by recurrence relation
$T(n) = {n-1 \choose l}*f(l)*f(r)$, where $l$ is number of nodes in left sub-tree.
Number of max heap possible with 1 key is 1 therefore $T(1) = 1$

Similarly number of max heap possible with 2 key is also 1, $T(2) = 1$

$T(3) = {2 \choose 1} *T(1)*T(1) = 2*1*1 = 2$

$T(4) = {3 \choose 2}*T(2)*T(1) = 3*1*1 = 3$

$T(5) = {4 \choose 3}*T(3)*T(1) = 4*2*1 = 8$

Therefore ans is 8.

2 Comments

you can derive $l$ and $r$ from $n$ right?
1
1

@gatecse yes sir we can.

0
0