CareerCup

This is same as finding Least Common Ancestor for A and B.

Approach: It is stated that node has child and parent properties. We can make use of parent property.
1. Start traversing from both the nodes using parent pointers'
2. For any one node, start pushing the nodes traveled in a hashtable. For another node traversal, keep check the node is present or not in hashtable. If node is present the found which is LCA of two nodes.
Probably have to work out the details where one traversal finishes before the other one but that can be easilly handled in the code.

If we want to avoid using any extra memory, we can treat this two list with one merging point. Which can be easily solved in O(h).

@Karthik is nailed it -- LCA problem. Greatly simplified LCA problem because we have a parent link. As such all that is necessary is:

- get depth of A (logN) by walking up
- get depth of B (logN) by walking up
- take deeper one and level with another one
- walk in parallel until they meet

We can achieve it using extra space O(P)
where P = size of path between A & B.
Algorithm:

1.Node a = A;
2.Node b = B;
3.Map<Node,Node> path = new HashMap<Node,Node>();
4.while(a.p != null && b.p != null && a != b){
	if(!path.contains(a)){
		path.put(a,a.p);
		a = a.p;
	}else if(!path.contains(b.p)){
		path.put(b.p,b);
		b = b.p;
	}else{
		return path;
	}
}
//Map maintains elements in insertion order.
5.return path;

How about this (please let me know if this seems sound)

N1 = A
N2 = B
Hash H{} = null
Pathfound = false
CommonParent = null;

while patfound = false do
  if N1.Parent is not null and N1.Parent exists in H then
    PathFound = true;
    CommonParent = N1.Parent
  end If
  H = H union N1.Parent

  if N2.Parent is not null and N2.Parent exists in H then
    PathFound = true;
    CommonParent = N2.Parent
  end If
  H = H union N2.Parent
end while

Pseudo Code Desc:

Copy Node A,B to N1 and N2
Create empty Hash H
PathFound
We assume parent of root is null

Explanation:

Path = Node1 to Common Ancestor + Node2 to Common ancestor
We walk upward from both child nodes simultaneously. We check Both parents in a Hash first, and if not found we add the parent. Since we use hash table, we can assume checking and adding both parents can be done in constant time.

Ideal Case: both nodes are at a distance of 1 from a common ancestor
Will befound out in 1 step
Worst Case: One is the root and other is farthest leaf, will take P steps
Other Avg cases: One is a close node, other is a deep seeded node, will take less than P steps as Common Ancestor will come before P steps or exactly P steps if one is parent of other

In the end we will have common ancestor node. We traverse from each node to common ancestor (total of P steps again and find the path by traversing one of the paths from node to ancestor, the other in reverse)

This takes : P steps for finding ancestor, P steps to construct path from both nodes to ancestor, and P steps to traverse path. So 3P steps or O(P) when simplified.