Goldman Sachs Interview Question
Country: United States
Step 1- Root will be one of the Ancestor for sure.
Step 2- if nodeA is less than root and node B is greater and vice versa than root is the only Ancestor , if not than repeat the same process for descendent nodes you will get the Ancestor nodes.
Lets say there are two node given 'F' and 'P'
-Find the traversing path for 'F'
[Path_1] Root => 'A' => 'B' => 'D' => 'F'
-Find the traversing path for 'P'
[Path_2] Root => 'A' => 'B' => 'G' => 'L' =>'P'
-Compare both of the path and find the last same node in both path
---- A and B are common in both of the path, hence B is the common parent for both node 'F' and 'P'
Node commonAnsctr(Node nodeA,Node nodeB, Node root){
if(root==null||nodeA==null||nodeB==null)
return null;
//find node for A in the tree
Queue q=new Queue();
q.enqueue(root);
int depthA=0;
int depthB=0;
Map<Node,Node> map=HashMap<Node,Node>();
while(!q.isEmpty()){
Node p=q.dequeue();
if(p==A)
nodeAfound=true;
if(p==B)
nodeBfound=true;
if(!nodeAfound)
depthA++;
if(!nodeBfound)
depthB++;
if(nodeAfound&&nodeBfound)
break;
if(p.left!=null){
map.put(p.left,p);
q.enqueue(p.left);
}
if(p.right!=null){
map.put(p.right,p);
q.enqueue(p.right);
}
}
//error condition if one of the node is not in the tree
if(!nodeAfound||!nodeBfound)
return null;
Node backtrackNode=null;
//which is one is the closest node
if(depthA<depthB){
//node a is closest node to root
backtrackNode=nodeB;
}else{
backtrackNode=nodeA;
}
int min=Math.min(depthA,depthB);
int max=Math.max(depthA,depthB);
//backtrack they both come to the same level
while(max!=min){
backtrackNode=map.get(backtrackNode);
max--;
}
//now when both are at the same level
//independent of they are on both side or at the different side of their common ancestor, they will converge to the same point
//case 1: they are at the same side
if(backtrackNode==nodeA||backtrackNode==nodeB)
return map.get(backtrackNode);
else{
//case 2 they are different side of the ancestor-node
//backtrack there till they have common ancestor
Node anotherBckTrckNode=(backtrackNode==nodeA)?nodeB:nodeA;
while(anotherNode!=backtrackNode){
backtrackNode=map.get(backtrackNode);
anotherBckTrckNode=map.get(anotherBckTrckNode);
}
return anotherBckTrckNode;
}
return null;
}
How about using Pre-order traversal of the tree..? The order of the tree does't really matter ..
So here's the really pseudo-code:
1. Start Pre-order traversal of the tree and traverse until you find an 'x' in [A,B].
2. When x is found record it as the tentative ancestor.
3. Continue traversal at 'x', if the other node is found within 'x', then 'x' is the common ancestor (assuming a node can be its own ancestor).
4. Else, update the tentative ancestor to a node's parent whenever backtracking from it using the stored parent-reference.
5. When the other node is found, the tentative-ancestor is the common ancestor.
Let us know if u see problems with this.
1. Find path from root to node A using DFS. Say it is 'root' -> P -> Q -> R -> S -> A
2. Find path from root to node B using same DFS. Say it is 'root' -> P -> Q -> R -> X -> B
3. Iterate both lists keeping two pointers, cur and prev.
4. Keep iterating until you reach a point where cur is different for path(A) and path(B).
5. prev is your answer.
Start from root.
- Jay October 22, 2013Check whether A and B are on the same side of the subtree.
if they are on the different sides, then the node is the common ancestor