CareerCup

We need to remove two edge with least weight. Here is how we can do this:
Traverse the tree breadth wise (use queue). Keep two variable to store MinNode1 and MinNode2. At the end remove the two least weight edge.
Pseudo code:
1. Queue.enqueue(root)
2. while (!queue.Empty())
2.1 poppedNode = queue.dequeue();
2.2. if(poppedNode->Left != null) queue.enqueue(popped->left);
2.3. if(poppedNode->Right != null) queue.enqueue(popped->Right);
2.4 if ( popped->Wt < = Max(minNode1->Wt, maxNode->Wt))
Swap (larger(minNode1, minNode2), popped);

At the end, remove the link : minnode1->parent and minnode1->parent

Clearing Ambiguity and responding to this question here.

Certainly we need to assume that the tree Has to be Binary Tree to be possible. So the algo goes here.

We need to create a Binary Tree on the basis of edge weight value as node and do the following operation.

1> For Unorder Binary Tree, we need to traverse the full tree to get the following values
a> Smallest Edge Node Value and Second Smallest Edge Node Value. As node is now edge.
b> Total Weight of the Tree
So the Max value will be Total minus the two smallest Node value and there will be three sub tree.
Time Complexity will be O(n) and Space O(1).
2> For Ordered Binary Tree like BST the algo remain the same only the Time Complexity goes to O(log n) as searching for the two smallest edge will be easier.

Please elaborate more with example.

This question is ambiguous. We can't always break a tree into three trees by removing two edges. Consider the following example:

A->B
A->C
A->D
A->E
A->F

In this case even after removing two edges, there will be only one and one tree

Such questions are expected from Microsoft only. I hate them.

max flow min cut theorem

This question is very ambiguous. Can someone clarify this question.?