The Gateway to Computer Science Excellence
+7 votes
1.1k views

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

in Combinatory by Boss (10.2k points)
recategorized by | 1.1k views
0
@higgs

not clear....can you explain a bit more
0
+1

I'm just elaborating the ans. given here: https://stackoverflow.com/questions/11845126/number-of-binary-heaps-from-1-n


n=1: {1}                                                 1  Max heap possible.


n=2   {1,2}                2 (parent)             1 Max heap possible.         

                                   |

                                  |

                                 1 (child)


n=3 {1,2,3}              3                                 3                                2 Max heaps possible

                              /      \                          /         \

                           1         2                     2            1

We can observe largest element will always be present at the root.


n=4 {1,2,3,4}             Let's pay a bit attention to the structure of the max heap with 4 nodes.

                                   It will be something like this:

                                               O

                                           /        \

                                       O            O

                                    /

                                 O

From our observations we have seen that the largest element will be placed at the root.

Therefore, we are sure that heap will be something like this:

                                              4

                                           /        \

                                       O            O

                                    /

                                 O


+3

(contd.)

What to do next??

    --- We know that, If M is a Maxheap, then its left and right subtrees also need to be max heaps.

Let's focus on left subtree now.

                                              4

                                           /        \

                                                  O

                                    /           

                                             

We have 3 elements remaining {1,2,3} //4 has been already been selected as the root of the original tree.

Our subtree is madeup of 2 elements.

We already know, max heaps possible with 2 elements  = 1

Let's put all this together.

           We need 2 elements to construct our left subtree.

           we have 3 elements.

           We have $\binom{3}{2} ways$ of choosing 2 elements from 3 elements and build our left subtree.

          (Only condition on left subtree is that it should be a max heap itself.)

          i.e. no. left subtrees that are max heaps = $\binom{3}{2} ways$ . No. of max heaps with 2 elements.

                                                                            = $\binom{3}{2} ways$ . f(2)

                                                                            = $\binom{3}{2} ways$ . 1

                                                                            = 3

       i.e. our 3 possible left subtrees are:

                                                       3                   3                2

                                                      /                     /                /

                                                   1                    2                1



0

(contd.)


Now we are left with one element only.

       No. of possible right subtrees = $\binom{1}{1} ways$ . No. of max heaps with 1 elements.

                                                       = 1 . 1

                                                       = 1


i.e. No. of max heaps with 4 elements = 1 . $\binom{3}{2}$ . f(2) . $\binom{1}{1}$ . f(1)

                                                                  ^        ^      ^

              1 way to  Choose root _________|          |        |

 No. of ways to choose elements in left subtree|        |

            No. of max heaps possible in left subtree____|         and so on.....

i.e. 3 possble max heaps with 3 elements are:

            4                                               4                                        4                                                                                   

         /     \                                          /    \                                     /   \                                

      3        1                                     2       3                                3     2                                        

    /                                                /                                           /                                       

 2                                                1                                          1                               

+4

(contd.)


n = 5 {1,2,3,4,5}     We know maxheap with 5 nodes will be something like this:

                                               5   //we know largest element will be selected as root.

                                           /        \

                                       O            O

                                    /    \

                                 O      O

No. of max heaps = 1 . $\binom{4}{3}$f(3) . f(1)

                              = 4 . 2. 1

                              = 8



n = 6 {1,2,3,4,5,6}     We know maxheap with 6 nodes will be something like this:

                                               6   //we know largest element will be selected as root.

                                           /        \

                                       O            O

                                    /    \           /

                                 O      O       O

No. of max heaps                                  = 1 . $\binom{5}{3} .  $f(3) . f(2)

                                                                  ^   ^       ^       ^
                                                                           \
              1 way to  Choose root _________|        |      |        |

No. of ways to choose elements in left subtree|    |        |

       No. of max heaps possible in left subtree____|         |

            No. of max heaps possible in right subtree__ ___|

                              = 1. 10 . 2. 1

                              = 20

and so on....
 



Can you solve the given problem now??

+1
@higgs

beautiful :) thanks
0

A_i_$_h  What is the anwer given?

+1

Higgs

Explanation is too good...thanks...

0
vishal...896 is correct
0

@hs_yadav

How it is correct ?

0
i think u got it?
0
It does not have explanation. I know answer i need explanation.
+1

Answer: 896

0
I got 200

what's the answer given ?
0
896
0
i m getting 224 ?
+8

$\frac{9!}{9*5*3*3*1*1*1*1*1}=896$

follow this he derived this formula beautifully. 

+1

@Shubhgupta

Can you share exact time in video its 1hr video

0
just play brother it will play from that point only and watch from 40:00.
0

@ShubhguptaBut why isn't 2018 question following this logic as for that also we could have only 1 structure but the ans for it is 80

 

0

just check the beautiful explanation by KAPIL sir https://gateoverflow.in/102171

if you have still doubt then comment !

+1

@Markzuck

it is working for 2018 examples also they asked # of min heaps ..so we have to consider CBT structure with 7 nodes

                    O

           O                  O

O                O   O                O

7! / 7*3*3*1*1*1*1 = 80

0
@Shaik Masthan sir,
So is Kapil sirs solution always results same as the above logic?
Means write n!/ N1*n2 and so on
Means dividing with the product of all the size of each node subtree?
0
0
just wow for this guy

4 Answers

+27 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)

by Boss (10.9k points)
+5 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

by Boss (11.7k points)
+1
Thanks

Really helpful source.
+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)

by Junior (939 points)
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

by Junior (625 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
198,496 comments
105,265 users