Closest Common Ancestor of a Node in a Tree

Problem Statement

You have a tree data structure. The ancestors of a given node are defined to be the node itself, its direct parent, or the ancestors of the parent node. The root node has no parent and is its own only ancestor. Write an algorithm that takes any two nodes and gives their closest common ancestor.

Evaluation

• Completeness of the pseudo-code algorithm (25%)


• Correctness of the algorithm, demonstrated by quick manual unit tests (25%)


• What is the time and space complexity of your algorithm? (25%)


• Is the most efficient solution, O (lg n), offered? (25%)

Solution

This is a basic data transformation problem. The key insight is when the interviewee realizes that transforming the problem is important.

• Weak candidates start from one node, and try all sorts of weird ways to go up the tree and then turn around.


• Intermediate candidates start from both nodes at the same time, go up the tree while tracking visited nodes, and stop when one path intercepts the other.


• Very strong candidates see the path from each given node to the root of the tree as a stack. Build the stack starting from one node all the way to the root. Do the same with the other node. Now you have two stacks with the root node on top of both. Start popping as long as the top (peek) of the stacks are the same. As soon as they're not, the last common node that you popped off the stack is the closest common ancestor.

References

Ron Logan asked me this question in my interview with Microsoft