Self Doubt

Question

How many min heap possible with 6 distinct node?

Answer 1

The answer is 20.

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

Answer 2

$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$