LowestCommonAncestorOfaBinarySearchTree.java

/**
 * Lowest Common Ancestor of a Binary Search Tree (BST)
 *
 * <p>Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the
 * BST.
 *
 * <p>_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5 Using the above tree as an example,
 * the lowest common ancestor (LCA) of nodes 2 and 8 is 6. But how about LCA of nodes 2 and 4?
 * Should it be 6 or 2?
 *
 * <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).�� Since a node can be a descendant of itself, the LCA
 * of 2 and 4 should be 2, according to this definition.
 *
 * <p>Hint: A top-down walk from the root of the tree is enough.
 */
public class LowestCommonAncestorOfaBinarySearchTree {
  public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) return null;
    if (Math.max(p.val, q.val) < root.val) return LCA(root.left, p, q);
    if (Math.min(p.val, q.val) > root.val) return LCA(root.right, p, q);
    return root;
  }
}