I was asked this interview question on my onsite round 1 . I found it very difficult if anyone have solution please help !!.

Looks like DP question Since we have multiple possibilities, but how to perform on Tree ?

given a binary tree, with each edge having a cost associated. we want to cut the edges in such a way that all the leaf nodes get disconnected from root which is 6. find the min cost.

eg.
6
/ \
4 2
/
1
weight 6 - 4 = 5,
weight 6 - 2 = 2,
weight 4 - 1 = 1

answer should be 3 (we will remove edge 4-1 & 6-2 so the all leaf nodes are disconnected from the root which is 6)

e.g 2

6 - 3: Cost 4
6 - 5: Cost 2
3 - 7: Cost 3
3 - 8: Cost 5
5 - 4: Cost 1

Ans : 5 (In this case you have to disconnect edge 5-4 & 6-3 to get minimum cost)