+1 vote
273 views

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 ________

asked in DS | 273 views

Suppose consider 15 elements 1,2,3,4,....15.

It is min heap ,level by level elements are stored.Root is at 1st level.

1st level; 1

2nd level: 2,3

3rd level: 4,5,6,7

4th level: 8,9,10,11,12,13,14,15.

In the second level elements are nodes 2,3 occupies 2 ways.no matter because it satisfies the heap property.

In the 3rd level also same nodes are 4,5,6,7 can be arranged in 4! ways.

In the 4th level 8!

SO TOTAL NO OF TREES ARE 1!*2!*4!*8*=1935360

What about a heap like this:

1st level: 1

2nd level: 2 5

3rd level: 3 4 6 7

4th level: 8 9 10 11 12 13 14 15

This is also valid according to the question but the answer does not account for these type of heaps.
i miss it,but this type of problems construct every min heap tree construction is so difficult.

so i think nearest no of min neaps consideration is better.
This is worng.Level 2 needn't have 2,3 the.The other valid combinations are 2,4 and 2,5

https://gateoverflow.in/100154/heap

refer this one.. this handles the said cases also.

Ans should be 8!*7! max 8 values will be tere in leaf, there are 8 nodes they can be arrange in any way and 7 in non leaf they can be arrange in any way.