Random

Question

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?

Comments

i got 2560

---

Ans is

4*C(7,6)* 80*C(4,1)*2

---

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.

Answer 1

 

Comments

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

---

@shub2204 after choosing 3 elements, min will be at root and another 2 we can arrange
iii 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

---

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👍