Bankbazaar Interview Question
Country: India
Interview Type: Phone Interview
Keep 2 stacks, s1 and s2.
For node 1, traverse down to the root while push Nodes onto the s1 until the root is on top of the stack.
For node 2, traverse down to the root while push Nodes onto the s2 until the root is on top of the stack
Now, pop from both stacks and compare ancestors. If the Nodes popped are the same, it is a common ancestor, so record this as the current ancestor. when it comes to nodes popped that are not the same, we have a reached a non-ancestor. Return the current ancestor to get the least one.
The problem actually whats to find out the first common node in two single lists.
- chshda March 26, 2015For both nodes, traverse down to the root to get their lengths, let's say the length of node 1 is len1, the length of node 2 is len2, and len1 < len2.
Let p and q point to node 1 and node 2 respectively, q moves forward len2-len1 steps first, then p and q both move step by step until they reach the same node, which is their lease common ancestor.