Redirected
edited by
7,277 views
17 votes
17 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_________________
edited by

8 Answers

Best answer
30 votes
30 votes

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

selected by
3 votes
3 votes
  1. 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$.
  2. This is straight forward, the total number of ways is $\frac{15!}{15\times7^2\times3^4}=21964800$.
2 votes
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

1 votes
1 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

Related questions

0 votes
0 votes
1 answer
2
Shubham Aggarwal asked Aug 29, 2018
356 views
5 votes
5 votes
0 answers
3
vamp_vaibhav asked Dec 29, 2017
557 views
Answer given : 1935360 but I m getting 3225600 please check..