Lowest Common Ancestor in a Binary Search Tree.

Question : 

Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree. (GeeksForGeeks)

LCA(Lowest Common Ancestor) :

From Wikipedia 

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself). 

The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor. (Source Wiki) 

Example :

For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.

Solution :

We can solve this problem using BST properties. We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node's value is greater than both n1 and n2 then our LCA lies in left side of the node, if it's is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)

Code : 

package Tree;

/**
 * Created by Aniket on 2/22/14.
 */
public class LCAFinder {

    public static TreeNode findLCA(TreeNode root, int n1,int n2){

        if(root == null){
            return null;
        }

        int data = root.getData();
        if(data > n1 && data > n2){
            return findLCA(root.getLeftNode(),n1, n2);
        }

        if(data < n1 && data < n2){
            return findLCA(root.getRightNode(), n1, n2);
        }
        return root;
    }

    public static void main(String args[]){

        TreeNode root = new TreeNode(20);

        TreeNode l = new TreeNode(8);
        TreeNode r = new TreeNode(22);

        TreeNode ll = new TreeNode(4);
        TreeNode lr = new TreeNode(12);

        TreeNode lrl = new TreeNode(10);
        TreeNode lrr = new TreeNode(14);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        System.out.println("LCA : " + findLCA(root,10,14).getData());
    }
}

Output : 

LCA of Node with data 10 and 14 : 12

(You can similarly execute the code for 8 and 14( Answer is 8))

Important Links : 

1. Lowest common ancestor
2. How to find the lowest common ancestor of two nodes in any binary tree?
3.  Lowest Common Ancestor in a Binary Tree. (OSFG)