3.8 Lowest Common Ancestor

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

  4
 / \
3   7
   / \
  5   6

• LCA(3, 5) = 4
• LCA(5, 6) = 7
• LCA(6, 7) = 7

Logical Steps

"Return whatever hit targets until both left and right of root hit both targets"

1. If root is A or B, return root directly
2. Divide
3. If left and right node of root are both not null, than root is lowest ancestor, return root
4. If root is not lowest ancester, if left or right is not null, return left or right (hit one target only)
5. If left and right are both null and root itself doesn't hit anything, return null

Code Example

/**
 * @param root: The root of the binary search tree.
 * @param A and B: two nodes in a Binary.
 * @return: Return the least common ancestor(LCA) of the two nodes.
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
    // base case: root is null or root is A or B
    if (root == null || root == A || root == B)
        return root;

    // divide
    TreeNode left = lowestCommonAncestor(root.left, A, B);
    TreeNode right = lowestCommonAncestor(root.right, A, B);

    /** conquer
     * the first "left and right both not null node"
     * will be returned as LCA
     */
    if (left != null && right != null)
        return root;

    if (left != null)
        return left;

    if (right != null)
        return right;

    return null;
}

Common Mistakes

1. Forget to return root when both left and right hits target

    // this is returning LCA, dont forget this
    if (left != null && right != null)
        return root;