424 views

2 Answers

Best answer
2 votes
2 votes

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

edited by
2 votes
2 votes
$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$

Related questions

0 votes
0 votes
1 answer
1
Ayush Upadhyaya asked Jun 3, 2019
393 views
How in a heap there are at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of height h.
0 votes
0 votes
1 answer
2
eyeamgj asked Oct 16, 2018
322 views
what is correct definition m=of max heap?every node should be greater than its childrenorevery node should not be smaller than its children
0 votes
0 votes
1 answer
3
Deepanshu asked Sep 12, 2018
624 views
If you are given a sorted list with n elements in ascending order. Then what will be the Time complexity to build a Min heap from the given array?