LCA of two nodes in a Binary Tree

Ah, this question has bugged me a lot. Finally I have found an answer to this. Actually there are two standard ways of doing this :

a. Do a Euler Walk on the tree and get the RMQ algorithm to calculate the LCA – cool, but for Ph,D. Students.

b. Create two array/linked list/queue and store DFS path to both the nodes and store them in these arrays. The last match in these arrays will be LCA. This solution is more practical than the first one. But the problem is how to get the DFS paths efficiently in a non BST binary tree ? If you know how to do that, please let me know in the comments.

After some research, I found a way which is smart and easier to understand.

Lets take the following tree.

We want to find the LCA for nodes – 4 and 7. LCA would be 6.

Algorithm :

We want to find the LCA of two nodes a and b.

1. Call the method LCA recursively on the left and right sub-tree. If both calls return ‘1’, it means that the current node has the parent of the left and right child and hence current node is the LCA.

2. The node that gets a ‘1’ from either left or right sub-tree returns back 1 to the parent. This node is not the parent yet but he is in the right path.

3. We need to take care of a special care where a is the parent of b or vice versa. In this case, we return 2 from one side and 0 from the other.

Code :

public static int findAncestor(Node node, int a, int b){
       if(node==null){
           return 0;
       }
       //Recursive calls to left and right sub-trees
        int l = findAncestor(node.left, a,b);
       int r = findAncestor(node.right, a,b);
       if(l==1 && r==1) //We found the LCA
        {
           System.out.println("LCA - " + node.data);
       }
       if((l==1 && r==0) || (l==0 && r==1)){
           //We found one of the element under this parent
            return 1;
       }
       if((l==2 && r==0) || (l==0 && r==2)){
           return 2;
       }
       else  //when l==0 and r==0
        {
           int matchRoot = (node.data ==a || node.data ==b) ? 1 : 0 ;
           return (l + r + matchRoot);
       }
   }