# Write a prograom to find LCA of two nodes in a binary search tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes(x1,x2) in the BST.

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). ```In the above example LCA of 3 and 7 is 5 .
LCA of 3 & 12 is 10.
LCA of 14,12 is 14.```

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.

To solve the problem, one need to traverse the tree recursively starting from parent node. The first node x encountered such that x1 <x < x2 or (x1 == x || x2 == x) is the LCA of the BST

``````public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}else if(root.val < p.val && root.val > q.val){
return lowestCommonAncestor(root.right, p, q);
}else{
// this means, either p.value == root.value or q.value == root.value
// or p.value < root.value < q.value
return root;
}
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}``````