Lowest Common Ancestor for a given pair of nodes

Question

Hi Guys,

I am stumbled by this question. The following is my approach:

Lets say the two nodes are node1 and node2
For any node (lets say node1), find the path from Root to 
      node1 and store it in an HashMap
For the other node node2, find the path from root to node2, and while traversing back, 
      check if any of the nodes are present in the hashmap or not
Return the first found node

Time Complexity is O(n) and Space Complexity is also O(h), where n is the height of the tree

I just wanted to know how good is this approach. Or whether there exists any other better solution.

EDIT: The given tree is Binary Tree and not BST. So, the time taken to find a node is linear to the size of nodes.

Answer 1

How's the tree represented? In particular, is there a reference to the parent node of any tree node? Is it an ordered tree?

Isn't it simpler to calculate the paths from node to root, then compare the paths from root to node? The last node that's the sanme on both paths is the common ancestor.

I think finding the path from root to node (as your approach has it) is O(n) where n is the size of the tree, unless the tree is ordered...

So your approach works, but if I were asking you the question I would have expected you to ask some additional questions about the layout of the tree in order to determine the correct answer...

Answer 2

If you only need to do this once (or a few times), then this is a good method (you could optimize by going from the nodes towards the root, if possible). If you need to do this a lot of times for different pairs of nodes, it's worth to spend a bit more time precomputing certain things, which will speed up queries.

I think this article explains things very well. Post back if you have any questions please.

Answer 3

Here is an instruction to solve Lowest Common Ancestor problem.

[Range Minimum Query and Lowest Common Ancestor][1]

[1]: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest Common Ancestor (LCA)