retagged by
38,692 views
67 votes
67 votes
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
retagged by

14 Answers

7 votes
7 votes

Let's note down the facts first.
- The smallest element will be on the least level.
- The second smallest element will be on the first level.
- The third smallest element can be on the second or third level.

Root is fixed, the idea is to divide the building process into two subproblems, each solving both subtrees of the root. 
Recurrence equation: T(n) = $_{k}^{n-1}\textrm{C}$ x T(k) x T(n-k-1), where k is number of nodes in left sub tree.

T(1) = 1

T(2) = 1, one root and one child.

T(3) = $_{1}^{2}\textrm{C}$ x T(1) x T(1) =  2

T(4) = $_{2}^{3}\textrm{C}$ x T(2) x T(1) =  3 

T(5) = $_{3}^{4}\textrm{C}$ x T(3) x T(1) =  8 

T(6) = $_{3}^{5}\textrm{C}$ x T(3) x T(2) =  20

T(7) = $_{3}^{6}\textrm{C}$ x T(3) x T(3) =  80

To put it down simply,  Among 7 elements, least element is fixed as root.
We are now left with 6 elements, the left subtree will have 3 elements, which can be picked in 
$_{3}^{6}\textrm{C}$  x 2 ways.
Now we have 3 elements remaining and we can complete the heap in 2 ways only.
Hence $_{3}^{6}\textrm{C}$ x 2 x 2 = 80.

6 votes
6 votes
f(1) = Number min heap with 1 node = 1
f(2) = Number min heap with 2 node = 1
f(3) = Number min heap with 3 node = 2    //swap left and right subtree

 

For a complete binary tree with n nodes number of nodes in left subtree (x) =
floor {((n-1)/2) + 1}.

1 node for Root (1 choice minimum valued node), x out of n-1 (leaving 1 for root) number of nodes in left subtree and n-1-x number of nodes in right subtree:
 So, the number of arrangements possible:
Select root, Select and arrange x nodes in left subtree, arrange n-1-x nodes in right subtree
C(n-1, x)*f(x)*f(n-1-x)

Let number of arrangements are f(n):
f(n) = C(n-1, x)*f(x)*f(n-1-x)

Put n==7
f(7) = C(7-1, 3)*f(3)*f(7-1-3) = C(6,3)*f(3)*f(3) = 20*2*2 = 80
edited by
5 votes
5 votes
One more way to solve this problem could be  $^6C_3*2*2 = 80$
Answer:

Related questions