LowestCommonAncestorBST.java

package tree;

/**
 * Created by gouthamvidyapradhan on 09/03/2017. Given a binary search tree (BST), find the lowest
 * common ancestor (LCA) of two given nodes in the BST.
 *
 * <p>According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined
 * between two nodes v and w as the lowest node in T that has both v and w as descendants (where we
 * allow a node to be a descendant of itself).”
 *
 * <p>_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5 For example, the lowest common
 * ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node
 * can be a descendant of itself according to the LCA definition.
 */
public class LowestCommonAncestorBST {
  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  public static void main(String[] args) throws Exception {}

  private TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;

    if (p.val == root.val || q.val == root.val) return root;
    else if ((p.val < root.val && q.val > root.val) || (q.val < root.val && p.val > root.val))
      return root;
    else if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    else return lowestCommonAncestor(root.right, p, q);
  }
}