Lowest common ancestor of two nodes in a binary tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes(x1,x2) in the binary 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).

In the above example LCA of9 & 6 is 2 .

LCA of 5 & 7 is 1.

LCA of 11,12 is 7.

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 == null || root == p || root == q)  return root;
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  if (left != null && right != null)
    return root;
  return left == null ? right : left;
}
class TreeNode {
  int value;
  TreeNode left;
  TreeNode right;
}