Amazon Interview Question
Analystsone important case to consider. We'll have to back up till both nodes reach the same depth. Then, move one step at at time for each node till we reach the common ancestor.
Node lca(Node left, Node right) {
while(left.depth() > right.depth()) left = left.parent();
while(right.depth() > left.depth()) right = right.parent();
while(left != right) {
left = left.parent();
right = right.parent();
}
return left;
}
Have three cases
- WA July 18, 2011First find the first node and second node
if the first node and the second node are on the left side keep moving left side and find it.
else if the two nodes are on the right side move right and keep on traversing it and find the ancestor.
if one node is on the right side and the other is on the left side keep two pointers traverse both side and keep track of the parent and find the ancestor.