The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7}exactly once is

Q. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7}exactly once is

Ans: 80

Sol:

Set minimum element as root (i.e 1), now 6 are remaining and left subtree will have 3 elements, each left subtree combination can be permuted in 2! ways. Total ways to design min-heap with 7-elements =

^6C_3 *2! * 2! = 20*2*2 = 80

Alternative approach –

Total number of min or max heap tree with 1 to N elements are using recurrence relation:

T(N) =(N-1)Ck * T(k) * T(N-k-1),

where k = number of nodes on left subtree

T(1) = 1

T(2) = 1

T(3) = 2

T(4) = 3C2 * T(2) * T(1) = 3

T(5) = 4C3 * T(3) * T(1) = 8

T(6) = 5C3 * T(3) * T(2) = 20

T(7) = 6C3 * T(3) * T(3) = 80

So, answer is 80.