9 votes 9 votes The number of min heap trees are possible with 13 elements such that every leaf node must be greater than all non-leaf nodes of the tree are ___ A. 627 B. 747 C. 657 D. 757 Programming in C test-series + – diksha kahensa asked Jan 6, 2017 diksha kahensa 1.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply Neha24 commented Jan 5 reply Follow Share @GO Classes What’s the correct ans of this question? Is it 7!*5C3*2C1*1 or 747? pls help 0 votes 0 votes Please log in or register to add a comment.
Best answer 15 votes 15 votes The number of min heap trees are possible with 13 elements such that every leaf node must be greater than all non-leaf nodes of the tree are $_{3}^{5}\textrm{C} \times 2! * 7!$ dd answered Jan 9, 2017 • selected Jan 9, 2017 by pC dd comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 1st level : 1 node => 1! ways 2nd level: 2 node => 2! ways 3rd level : 4 node => 4! ways 4th level: 6 node => P(8,6) ways So, number of Min Heaps are = 1!*2!*4!*P(8,6) = 672 Please cross ckeck ! Abhijit Borah answered Jan 7, 2017 Abhijit Borah comment Share Follow See all 20 Comments See all 20 20 Comments reply vijaycs commented Jan 7, 2017 reply Follow Share ^heap is complete binary tree ..right ?? So, why P(8, 6) at 4th level ?? I think, it should be - 5C3 * 2! * 7! = 1,00, 800. // assuming all non-leaf nodes are distinct. for details see - https://gateoverflow.in/102171/min-heap @Kapil , please check ..?? 0 votes 0 votes thor commented Jan 7, 2017 reply Follow Share I think it should be $7!*3!*2!$. 0 votes 0 votes Kapil commented Jan 8, 2017 reply Follow Share @vijaycs how $C(5,3)$ ? 0 votes 0 votes diksha kahensa commented Jan 8, 2017 reply Follow Share According to the solution provided, answer is Total min heap trees possible= 6! +4!+2!+1 = 747 What i didn't get is the no 7 can be present on 4th level also because all leaf nodes must be greater than non leaf nodes. so on leaf nodes permutation must be between 7 to 13 not from 8 to 13. Please clarify. 1 votes 1 votes thor commented Jan 8, 2017 reply Follow Share $7$ is also a leaf node. 0 votes 0 votes vijaycs commented Jan 8, 2017 reply Follow Share @kapil, see @diksha's tree...Where(according to question) node 7 to 13 are greater than all rest 1 to 6 elements right...??So we can not place any leaf nodes at non leaf and vice versa... Now we have to find total possible min heap with first 6 nodes. So for first six elements, total possible min heap= C(5, 3)*2! ... Correct me if I am wrong...?? 0 votes 0 votes Kapil commented Jan 8, 2017 i edited by Kapil Jan 8, 2017 reply Follow Share @vijaycs Total min heaps possible in this way => $7! * C(5,3) * 2! * C(2,2) * 1!$ 0 votes 0 votes vijaycs commented Jan 8, 2017 reply Follow Share * every leaf node must be greater than all non-leaf nodes of the tree. here total leaf nodes = 7 ..? so, we can permute in 7! for every min heap tree with first 6 elements. right ?? why are you considering only 6 leaf nodes ?? node at index 7 ( index starting from 1, ) is also a leaf node ..right ?? 1 votes 1 votes pC commented Jan 8, 2017 reply Follow Share @vijaycs see this https://gateoverflow.in/100154/heap?show=100266#a100266 1 votes 1 votes Kapil commented Jan 8, 2017 reply Follow Share @vijaycs, u r right . 1 votes 1 votes vijaycs commented Jan 8, 2017 reply Follow Share Thanks @pC , here we have total n = 13 nodes ( instead of 15 in the link ) and here we have total 7 leaf nodes ( and incase of n=15, leaf = 8) ..right ?? Now you please tell , where I am wrong.. ?? Acc. to me ans = C(5 , 3 ) * 2! * 7! ?? 3 votes 3 votes vijaycs commented Jan 8, 2017 reply Follow Share Thanks@Kapil : ) 1 votes 1 votes Kapil commented Jan 8, 2017 reply Follow Share They are adding and getting $747$ :) :D 0 votes 0 votes pC commented Jan 8, 2017 reply Follow Share @vijaycs ur correct . Actually 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 But when n=13 Like you said Node at index 7 will create problem 1 votes 1 votes pC commented Jan 8, 2017 i edited by pC Jan 8, 2017 reply Follow Share @kapil @vijaycs Can u check this ? I think 8! * C(6,3 ) * 2*2 = 3225600 is the answer here. 1 votes 1 votes diksha kahensa commented Jan 8, 2017 reply Follow Share @vijaycs u r correct I was having the same doubt why 7 was not considered as the leaf node. 0 votes 0 votes dd commented Jan 9, 2017 reply Follow Share pC if you doing it with recurrence please elaborate it clearly. 1 votes 1 votes dd commented Jan 9, 2017 reply Follow Share I guess you are talking about total possible heaps with 7 elements.. https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements 1 votes 1 votes dd commented Jan 9, 2017 reply Follow Share ........................ 1 votes 1 votes pC commented Jan 9, 2017 reply Follow Share infinte upvotes for this diagram . Never thought of this senario. Thanks for correcting me :) 1 votes 1 votes Please log in or register to add a comment.