# lowest common ancestor of a binary search tree

Following is definition of LCA 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).

Thus lca is guaranteed to exist if both the nodes are present in tree.  In any other case it is NULL. LCA of 4 and 5 is 3.
LCA of 2 and 5 is 1.
LCA of 3 and 5 is 3.

To find LCA , The below code assumes that both the nodes are present in the tree. To extend this algo for the cases that , it works even if only one of nodes are present in the tree, is left as an exercise to the reader.  There are 2 ways to do this – One is to check beforehand if the nodes are present in the tree or not. Other way to change our solution a bit to account to check if both the nodes are present. Like 2 variables which update when we find the nodes in finding LCA.

```//Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree

/* Class containing left and right child of current
node and key value*/
class Node {
int data;
Node left, right;

public Node(int item) {
data = item;
left = right = null;
}
public Node() {
data = 0;
left = right = null;
}
}

public class BTree {

Node root;

// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node LCA(Node node, int val1, int val2) {
// Base case
if (node == null)
return null;

// If either n1 or n2 matches with root's key, return root. Note this assumes that
// both thr roots are present in the tree. To extend this algo for those cases , which
//account if either of the node is present or not, is Left as an exercise for students.
if (node.data == val1 || node.data == val2)
return node;

// Look for keys in left and right subtrees
Node left_lca = LCA(node.left, val1, val2);
Node right_lca = LCA(node.right, val1, val2);

// If both the left_lca and right_lca is not null, that means this is LCA.
if (left_lca != null && right_lca != null)
return node;

// Otherwise check if left subtree or right subtree is LCA
if (left_lca != null)
return left_lca;
else
return right_lca;

}
public static void main(String args[]) {
BTree tree = new BTree();
tree.root = new Node(11);
tree.root.left = new Node(9);
tree.root.right = new Node(8);
tree.root.left.left = new Node(7);
tree.root.left.right = new Node(6);
tree.root.right.left = new Node(5);
tree.root.right.right = new Node(4);
System.out.println("LCA(9, 8) = " +
tree.LCA(tree.root, 9, 8).data);

System.out.println("LCA(11, 4) = " +
tree.LCA(tree.root, 11, 4).data);

}
}
```