MadeEasy Test Series: Programming & DS - Binary Tree

Question

Comments

.009 ?

---

Its 0.016

---

I'm getting 0.0158

Min heaps possible = 6C3 * 4  = 80

Total permutations = 7!

Probability = 80 / 7! = 0.0158 = 0.016 upto 3 decimal places

Answer 1

Min Heap

 

Comments

Bro in point number 2 you are taking 3! due to number of leaves right (arrangement)?

I am not understanding how u got 2 * 2! in 4th point.

How u got 71 at last ?

---

@Shamim Ahmed 

4th step: N1 fixed as 2 and N2 as 5 and child of N1 can be 3 and 4 i.e 2! and child of N2 can be 6 and 7 i.e 2!

hence 2*2! on next stage it i did N1 as 5 and N2 as 2.

at last it is not 71 it is 7! total possible arrangement it can have

 

Answer 2

so the Min heap is a complete tree.  With the given numbers {1, 2, 3, 4, 5, 6, 7}  the tree will be of the form 

         

 

so at the top will be 1 and in 2^nd level there is 2 and 3 which can be swapped hence 2 ways

At leaf there are 4,5,6,7 and they all can be permuted in 4! ways    

So total ways are 2*4!   

probablity  2*4! / 7!  =  0.009

Answer 3

Array element is {1,2,3,4,5,6,7} .

The number of all possible permutations in these elements = 7! .

Since, we have to satisfy min heap property, always root element is smallest among all the elements .

So, "1" should be root node. Remaining element is {2,3,4,5,6,7} .

Therefore, there are 3 elements out of 6 elements going to left subtree in 6C3 ways and remaining going to right subtree. Suppose, {2,4,5} going to left subtree and since, minimum element is 2 so, "2" should be root of left subtree. There are 2 remaining elements {4,5} being children of "2" in 2! ways [Either "4" would be left child of "2" and "5" would be right child of "2" Or "4" would be right child of "2" and "5" would be left child of "2"].

So, remaining elements {3,6,7} going to right subtree in 3C3 ways. Since, Minimum element is 3, so "3" should be root of right subtree. There are 2 remaining elements {6,7} being children of "3" in 2! ways. 

So, probability = (6C3 x 2! x 3C3 x 2! ) / 7!

                           = 1/63 = 0.016