CareerCup

Find LCA of 3 pairs - (a, b), (b, c) and (c, a)
LCA of at-least 2 pairs will be same.
If all 3 LCAs are same, remove that LCA node.
If only 2 LCAs are same, then we have two distinct LCA node here. One LCA node will be parent and other LCA node will be child. Remove the Child LCA Node (We may calculate height of the two LCA nodes here. The LCA node with lesser height will be the Child of the other and this lesser height node should be deleted).

Not Possible in a binary tree

1: Let x be the root of the three.

2: While either the left of right subtree of x contains two of {a, b, c} do:
3:     set x to its child whose tree contains two of {a, b, c}.

4: Return x.

As it has been remarked, we need to remove all edges that come from or go to node x returned by the algorithm. This is so because there might be a donw path (from root to a leave) containning nodes a, b and c. If not, then we need to remove just the edges coming from x.

The loop 2-3 is repeated at most h times where h is the height of the tree.

At each iteration we need to check which, if any,subtree of x contains a, b and c. The complexity of this check depends on the data strored at each node and how the tree was build. For instance, consider these three cases:

* The tree is a binary search tree: then a node y is in the left subtree of x if, and only if, key(y) < key(x) which has the complexity of a comparison, normally O(1). In this case the total complexity of the algorithm is O(h).

* Each node of the tree stores a pointer to its parent. Then, starting from a node y and going up the tree we stop until we reach x or the root. If we reach x then we can determine if we came from left or right. If we don't reach x, it means that y is not in the subtree of x. The time for walking up the tree from y is O(h), so the total complexity of the algorithm is O(h^2).

* None of the above. Then, from x, we can do a DFS to check if a node y belongs to the subtree rooted at x and, if so, on which side. This costs O(|E(x)|) where E(x) is the set of edges of the subtree rooted at x. Since it's a binary tree, |E(x)| = |V(x)| + 1 where V(x) is the set of vertices of the subtree rooted at x. In a well balanced tree, |V(x)| = O(2^h). Then the total cost of the algorithm is O(h * 2^h) = O(2^h).