edited by
3,728 views
7 votes
7 votes

MY SOLUTION :

Fix the root

then next level 2 elements ( 2! possibilities)

next level 4 elements( 4! possibilities)

last level 2 elements ( 2! possibilities)

total possibility = 2! * 4! * 2! = 2 * 24 * 2 = 96

what went wrong ?

just in case if the question in image is not clear

question -which of the follwing represents the total number of ordering possible with elements 12,10,8,5,3,2,1,7,9 such that if node of above graph is filled with these elements it satisfies max heap property

a)96

b)896

c)2688

d) none

edited by

4 Answers

29 votes
29 votes

Given Elements : 12,10,8,5,3,2,1,7,9

1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)

2) Remaining : 8 elements

Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)

3)Left Subtree :

Out of 5, maximum element is the root.

Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.

#Heaps possible in Left Subtree= 4C3 * 2 --->(3)

3)Right Subtree :

Out of 3, maximum is root.

Remaining 2 elements can be arranged in 2 leaves in 2 ways.

#Heaps possible in Right Subtree=  2 --->(4)

Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 )  * (3C3 * 2 )

=56 * 4 * 2 * 2 =896 (ANS)

6 votes
6 votes

The total number of ways we can arrange data in 9 nodes = 9!

Divide it be the number of descendants each node has including itself.

Like root has 8 descendent + itself so we have divided by 9. 

Source: https://youtu.be/1U3loHkX5XE?t=2260

3 votes
3 votes

Given Elements : 12,10,8,5,3,2,1,7,9

1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)

2) Remaining : 8 elements

Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)

3)Left Subtree :

Out of 5, maximum element is the root.

Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.

#Heaps possible in Left Subtree= 4C3 * 2 --->(3)

3)Right Subtree :

Out of 3, maximum is root.

Remaining 2 elements can be arranged in 2 leaves in 2 ways.

#Heaps possible in Right Subtree=  2 --->(4)

Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 )  * (3C3 * 2 )

=56 * 4 * 2 * 2 =896 (ANS)

0 votes
0 votes

 Consider element 12,10,8 and given B-tree. Find no.  of possible max-heap possible.                                                                                        a.png 

 

We have to find no. of possible max heap in this tree.We know that arrangements are 10,12,8 and 8,12,10    Mathematically, it should have been 3!, but what we are doing is  we are fixing 12 at position 2nd of array.

 ∴ We have to divide it by 3 to reduce what we earlier have multiplied to each element as we have now fixed one of them.

∴ no. of total possible arrangement after fixing = 3!/3 = 2

a.png          

 Again we will take 4 elements 10, 3, 4, 8 and a B-tree Find  no. of max-heap possible.

 

 

 

sol :  We will our intuition and logic as this problem is problem is small to draw all possible b-tree to be able to fill our max-heap requirements.

a.png      So, given is our three required Max-heap.     Mathematically, we will try. For 4 element total arrangement is 4!

   Now, in max-heap at any subtree root must have highest of all it’s node. So first we will fix largest of all element i.e. ‘10’ to top. Which make us divide by 4 to earlier 4! as element 10 must have multiplied to give 4! arrangements. But note 10 is fixing at a particular position in normal array it is position 3 which lead to 2 subarray. One having 2 element and second having 1 element. Now again we have 2 seat to left of element 10. Position 2 seat i.e. just left of root (10) will again occupy the bigger among two. So again we have to divide by 2 to above 4!. Now we are left with 2 subtree with each 1 element.

So. Total possible max-heap in this arrangement = 4!/4.2.1.1 = 3

So, Concept is in this type of question that first take n! then divide by n and then keep dividing by no. of nodes in subtree of each node starting from root.

So coming back to our question we will get :

          ∴    Possible no. of Max-Heap possible =     9! / 9.5.3.3 = 896

Related questions

2 votes
2 votes
1 answer
1
0 votes
0 votes
1 answer
2
UK asked Jan 28, 2016
907 views
Number of solutions are there of x+y+z=17 in positive integers are_________Here in this do we have to take constraints of x>=1,y>=1,z>=1?
1 votes
1 votes
3 answers
3
0 votes
0 votes
3 answers
4
snaily16 asked Jan 22, 2019
1,368 views
The number of ways 5 letter be put in 3 letter boxes A,B,C. If letter box A must contain at least 2 letters.