263 views
How many min heap possible with 6 distinct node?

See below image

OR

One way to select root.

10

/      \

LST (3 elements)    RST (2 elements)

Now LST contains an element out of 5 (As the root is chosen)

So Total ways to choose element  $_{}^{5}\textrm{C}_{3}$

and RST contains 2 element So number of ways = $_{}^{2}\textrm{C}_{2}$

Let LST chosen { 20,30,40}

Now 2 chosen as root of LST (in one way)

Now remaining 2 element can arrange in 2!

ie.      20              20

/       \          /      \

30        40   40        30

Therefore Total Possibility = $_{}^{5}\textrm{C}_{3}$  x 2! x $_{}^{2}\textrm{C}_{2}$

=  20

$T(n) = \binom{n-1}{L} \cdot T(L) \cdot T(n-1-L)$

Where $L$ is the number of nodes in the Left subtree of the root.

Note: The above equation also holds when we take $R$, number of nodes in right subtree of the root, instead of $L$.

Base condition would be, $T(1) = T(2) = 1$
by