Lowest Common Ancestor in a Binary Search Tree.

Given the values of two nodes in a binary search tree, we need to find the lowest common ancestor. You may assume that both values already exist in the tree.

I/P : 4 and 14

O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 <>

    private static int LCA(Node root, int x, int y){

       /* If we have reached a leaf node then LCA doesn't exist

          If root->data is equal to any of the inputs then input is

          not valid. For example 20, 22 in the given figure */

       if(root==null || root.data==x || root.data==y){

           return -1;

       }

       /* If any of the input nodes is child of the current node

       we have reached the LCA. For example, in the above figure

       if we want to calculate LCA of 12 and 14, recursion should

       terminate when we reach 8*/

       if(root.right != null && (root.right.data==x || root.right.data ==y)){

           return root.data;

       }

       if(root.left != null && (root.left.data==x || root.left.data ==y)){

           return root.data;

       }



       if(root.data > x && root.data < y){

           return root.data;

       }

       if(root.data > x && root.data > y)

       {

           return LCA(root.left, x,y);

       }

       if(root.data < x && root.data < y){

           return LCA(root.right,x,y);

       }

       return -1;

   }