Heap..

Question

1)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 ________.

--------------------------------------------------------------------------------------------------------------------------

2)The number of min heap trees are possible with 15 elements_________________

Comments

https://gateoverflow.in/100154/heap

---

answer given by Made easy is wrong, it must be 3225600

Answer 1

Let us take 15 elements [1,2,3,4.....15]. To satisfy the condition mentioned in the problem all the 8 largest element should come to the last level. means element {8,9,10,11,12,13,14,15} must come in the last level. 

So total no of ways to arrange the elements in the last level = 8!

now for the remaining elements {1,2,3,4,5,6,7} there are no restriction hence they can come in any order in min heap. Hence it will be equivalent  to construct the min heap using  elements {1,2,3,4,5,6,7}. = 80 ways. for this please see below. link http://karmaandcoding.blogspot.com/2012/02/number-of-min-heaps-from-array-of-size.html

hence total no will be = 80 * 8! = 3225600.

If the same question is little bit modified and let us say - The number of min heap trees are possible with 15 elements such that every node at a particular level must be greater than all the nodes of the tree which are above that level. ex. all the nodes present at level 3 must be greater than all the nodes present at level 2 and so on....

Then the explanation given by @Aman Chauhan seems more meaningful.

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

Comments

https://gateoverflow.in/100154/heap This seems like correct answer. Correct answer must be 3225600.

Answer 2

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.

Answer 3

Let us take 15 elements [1,2,3,4.....15]. To satisfy the condition mentioned in the problem all the 8 largest element should come to the last level. means element {8,9,10,11,12,13,14,15} must come in the last level. 

So total no of ways to arrange the elements in the last level = 8!

now for the remaining elements {1,2,3,4,5,6,7} there are no restriction hence they can come in any order in min heap. Hence it will be equivalent  to construct the min heap using  elements {1,2,3,4,5,6,7}. = 80 ways. for this please see below. link http://karmaandcoding.blogspot.com/2012/02/number-of-min-heaps-from-array-of-size.html

hence total no will be = 80 * 8! = 3225600.

If the same question is little bit modified and let us say - The number of min heap trees are possible with 15 elements such that every node at a particular level must be greater than all the nodes of the tree which are above that level. ex. all the nodes present at level 3 must be greater than all the nodes present at level 2 and so on....

Then the explanation given by @Aman Chauhan seems more meaningful.

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

Answer 4

The answer to this is

21964800
As we know it is a complete binary tree as number of elements are just 1 less than some power of 2.
So we can assume that our condition will always be met that leaves will be present in only last level and by default it will be greater than the above internal nodes.
So we can simply use the formula
14C7f(7)*f(7)
Which is 3432*80*80 = 21964800

 

The 80*8! answer is incorrect because, when you have 15 nodes, and it is a max heap, then there is not a single case where your leaf nodes are less than all the internal nodes.

By default, all the leaf nodes are greater than the internal nodes.

So answer is only 21964800