198 views

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.

by

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

@gatecse yes sir we can.

1
2,749 views
1 vote