MadeEasy Test Series: Programming & DS - Heap

Question

The number of min heap trees are possible with 15 elements such that every leaf node must be greater than all non-leaf nodes of the tree are ________.

Answer 1

at first level,there can be only 1..hence only 1 way

at second level,there can be 2 or 3 ,hence 2 ways

at third level,there can be 4,or 5 or 6 or 7 ,hence 4! ways

at fourth level,there can be 8 or 9or 10 or 11 or 12 or 13 or 14 or 15 ,hence 8! ways

so,total number of min heaps are 1*2* 4! * 8! ways . It looks like this ....

---

But actually, question only asks to handle leaf nodes not internal nodes, hence the numbers 2,3,4,5,6,7 can be arranged any way.

At root, 1 is for sure fixed, but for 2,3,4,5,6,7 , total ways will be 

$C(6,3) * 2! * 1 * 2! * 8! = 3225600 $ ways.

---

PS: $C(6,3)$ :- Choose any three elements for left $3$ positions and arrange them in $2!$ ways.

Then, right $3$ positions can be permuted in $2!$ ways .

Comments

http://karmaandcoding.blogspot.in/2012/02/number-of-min-heaps-from-array-of-size.html

Answer 2

is it 274560