The Gateway to Computer Science Excellence

+14 votes

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_________________

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

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

+28 votes

Best answer

1)i am getting 3225600

if numbers are 1,2,3,4...15,

level-1: can be arranged in only one way.

level-2: need to discuss

level-3: need to discuss

level-4: can be arranged in 8! ways. bcoz we need to choose highest 8 elements and rannage them here.

now we are left with 2 subtrees S1 and S2(shown in figure below)

and 6 elements 2,3,4,5,6,7.

take any 3 elements and you can arrange these 3 elements in 2 ways in the left subtree, now take the ramaining 3 elements and arrange them in 2 ways in right subtree. (in any 3 elements chosen, one will be the minimum among them, that one element will be the root and remaining two elements can be arranged in 2! ways as children of respective root)

6C3*2*3c3*2

total ways =(6C3*2*3C3*2)*8! = 3225600

2)

this in similar way, root can be arranged in one way

we will be left with 2 subtrees and 14 elements.

choose any 7 elements, minimum among them will be root of left subtree, this root has two subtrees same like previous problem, these two subtrees can be arranged in 6C3*2*3C3*2. so the entire left subtree of the main root can be arranged in 14C7( 6C3*2*3C3*2)

now coming to ryt subtree similar way,

here we choose 7 elements from the remaining. so number of ways of arranging this entire right subtree =7C7( 6C3*2*3C3*2)

total ways=14C7( 6C3*2*3C3*2)*7C7( 6C3*2*3C3*2)

dont know if this is correct. let me know if you find some mistake

0

but in 2)

14C7

u r choosing 1 subtree.

Say u choose left subtree.

Now, in 6C3 again u r choosing from left subtree and right subtree (from both)

Which should not be there

right?

14C7

u r choosing 1 subtree.

Say u choose left subtree.

Now, in 6C3 again u r choosing from left subtree and right subtree (from both)

Which should not be there

right?

0

sorry,i did not get your doubt

why 6C3 shudnt be there?

14C7- means i chose 7 elements from 14 elements to fill in left subtree. minimum of these 7 elements will be root of left subtree. i need to arrange two children of this left subtree. same like the 1st problem let left subtree be S1 and right subtree be S2. we will have 6 elements as we already arranged 1 elemnt in root. this becomes similar to first problem.

why 6C3 shudnt be there?

14C7- means i chose 7 elements from 14 elements to fill in left subtree. minimum of these 7 elements will be root of left subtree. i need to arrange two children of this left subtree. same like the 1st problem let left subtree be S1 and right subtree be S2. we will have 6 elements as we already arranged 1 elemnt in root. this becomes similar to first problem.

0

level 1 :1

level 2: 2,5

level3: 3,4,6,7

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

is it also maintaining in this solution?

level 2: 2,5

level3: 3,4,6,7

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

is it also maintaining in this solution?

0

@srestha,

Question 2

https://gateoverflow.in/102171/min-heap

Question 1

n=15 is a special case where we can solve this like

- last level nodes = 8 can be permutted in 8!
- Now the question reduces to The number of min heap trees are possible with 7 nodes

The story will be different when n is <15

see https://gateoverflow.in/101374/test-series

+2 votes

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**

+3

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.

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.

+1 vote

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*

0

no Anusha

See this line "every leaf node must be greater than all non-leaf nodes "

i.e why I added 2nd question

See this line "every leaf node must be greater than all non-leaf nodes "

i.e why I added 2nd question

+1

yes there are 4 levels.

4th level is leaf nodes level.

but, levels 2,3 are like normal heap ryt?

level 1 :1

level 2: 2,5

level3: 3,4,6,7

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

level -4 is greater than all other internal(non-leaf) nodes. this tree satisfies given condition isnt it?

4th level is leaf nodes level.

but, levels 2,3 are like normal heap ryt?

level 1 :1

level 2: 2,5

level3: 3,4,6,7

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

level -4 is greater than all other internal(non-leaf) nodes. this tree satisfies given condition isnt it?

0

It doesn't contain because you have to find out heap tree .which alwayz a Complete binary tree or almost complete binary tree so its not possible

+1 vote

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*

0

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

+1 vote

- The $8$
**leaf nodes**are always be last 8 elements in the sorted sequence (**increasing order)**. So these elements in these $8$ nodes can be permuted. Now there are $7$ non-leaf nodes remaining to make heap. For this case, there are $\frac{7}{7\times3^2}$ ways to make heap using the rest $7$ elements. So the total number of ways is $\frac{7!}{7\times3^2}\times 8!=3225600$. - This is straight forward, the total number of ways is $\frac{15!}{15\times7^2\times3^4}=21964800$.

0 votes

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.

0 votes

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 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*

52,375 questions

60,581 answers

202,000 comments

95,401 users