Lowest Common Ancestor of Binary Tree(Not Binary Search Tree)..

Question

I tried working out the problem using Tarjan's Algorithm and one algorithm from the website: http://discuss.techinterview.org/default.asp?interview.11.532716.6, but none is clear. Maybe my recursion concepts are not build up properly. Please give small demonstration to explain the above two examples. I have an idea of Union Find data-structure.

It looks very interesting problem. So have to decode the problem anyhow. Preparing for the interviews.

If any other logic/algorithm exist, please share.

Answer 1

The LCA algorithm tries to do a simple thing: Figure out paths from the two nodes in question to the root. Now, these two paths would have a common suffix (assuming that the path ends at the root). The LCA is the first node where the suffix begins.

Consider the following tree:

              r * 
               / \
            s *   *
             / \
          u *   * t
           /   / \
          * v *   *
             / \
            *   *

In order to find the LCA(u, v) we proceed as follows:

• Path from u to root: Path(u, r) = usr
• Path from v to root: Path(v, r) = vtsr

Now, we check for the common suffix:

• Common suffix: 'sr'
• Therefore LCA(u, v) = first node of the suffix = s

Note the actual algorithms do not go all the way up to the root. They use Disjoint-Set data structures to stop when they reach s.

An excellent set of alternative approaches are explained here.

Answer 2

Since you mentioned job interviews, I thought of the variation of this problem where you are limited to O(1) memory usage.

In this case, consider the following algorithm:

1) Scan the tree from node u up to the root, finding the path length L(u)

2) Scan the tree from node v up to the root, finding the path length L(v)

3) Calculate the path length difference D = |L(u)-L(v)|

4) Skip D nodes in the longer path from the root

5) Walk up the tree in parallel from the two nodes, until you hit the same node

6) Return this node as the LCA

Answer 3

A and B are the nodes in question.

seen := set containing root
while A is not root:
    add A to seen
    A := A's parent
while B is not in seen:
    B := B's parent
B is the answer.