0 votes 0 votes Consider a 15 element min-heap which follows these conditions. right child of root is7 and one child of node 3 is 9. Calculate how many min heap possible? DS data-structures binary-heap combinatory + – shub2204 asked Nov 30, 2022 • retagged Nov 30, 2022 by makhdoom ghaya shub2204 678 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kabir5454 commented Nov 30, 2022 reply Follow Share i got 2560 0 votes 0 votes shub2204 commented Nov 30, 2022 reply Follow Share Ans is 4*C(7,6)* 80*C(4,1)*2 0 votes 0 votes shub2204 commented Dec 1, 2022 reply Follow Share Basically root is fixed for 1 and right of root is 7. Since right of root is 7 then 2 should come as left node of root and 3 as any child of 2 , nine is child of 3 .so our tree will look like this Now 3 and 9 means root 3 and child 9 has 4 places to move so we are basically left with 8,10,11,12,13,14,15, these can come below 7 so selecting 6 out of 7 can be done in C(7,6) as root is fixed as 7, these 7 node subtree min heap can be made in 80 ways so we have 4*C(7,6)*80 Now we have 4 places left in left subtree below 2. So we can select 1 in C(4,1) and permute them in 2 ways. so Total ways: 4*C(7,6)*80*C(4,1)*2 ways I understood till here, but confused why we are not permuting in 3 ways for last multiplication. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Shoto answered Dec 1, 2022 • edited Dec 1, 2022 by Shoto Shoto comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments shub2204 commented Dec 1, 2022 reply Follow Share One question since in the last 4 nodes we are doing 4c3 but they can be arranged in 3 ways .. why we have taken 2. Why node marked with iii is left Can you please explain 0 votes 0 votes Shoto commented Dec 1, 2022 i edited by Shoto Dec 1, 2022 reply Follow Share @shub2204 after choosing 3 elements, min will be at root and another 2 we can arrangeiii is left because while selecting 3 out of 4 elements we are counting the cases when all 4 elements can be at iii in some combination 1 votes 1 votes shub2204 commented Dec 1, 2022 reply Follow Share Yes aditya.. i tried making all combinations .. since we are choosing 3 out of 4 then only we can satisy min heap .. taking smallest out of 3 and making it root and then permuting child and fourth will be simply put in place.. thanks a ton👍 1 votes 1 votes Please log in or register to add a comment.