265 views

Please explain the logic behind this shortcut and when to be used?

closed

closed | 265 views
0
From my observation :-  this is what they are doing.. total ways to arrange 9 numbers = 9!

For denominator, start from root node, visit every node and multiply the result with number of nodes present in that subtree.

Eg here for root node :- subtree has 9 nodes,

For left child of root :- subtree has 5 nodes,

For right child of root :- subtree has 3 nodes...

So on calculate for every node to obtain denominator.

You will get 9x5x3x3x1x1x1x1x1

Now Why are they doing this?
0

0

I don't understand what formula they have used. But to find the no. of max(or min) heaps from n elements we follow this approach:

If you don't get it then I'll try to explain..

0

@MiNiPanda Pls explain your way.. Actually, I was able to figure out answer of the above question using permutations and combinations but I want to know the answer for any general case tree.

+1

In similar way, 1st draw the structure of heap with 9 elements. There will be exactly one structure possible.

$H(9)= \binom{8}{5}H(5)H(3)$

P.S. I did for min heap but same approach will be for max heap.

+1
0
If anyone wants to do fast. just watch that video it will you to solve the question only in one minute.
0

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

@Markzuck

Please before posting the question, should check for Duplicates.

Due to you didn't check, everyone wastes their precious time for this discussion ( due to it is already solved and discussed in very clear manner )

1
+1 vote
2
+1 vote