Lowest Common Ancestor

Intro

This is classic problem of binary tree. It has a lot of practical usages and motivations behind it. For example, we want to find the lowest tag that two elements have access to in a DOM tree. Or we want to find the smallest interval in a segment tree.

LCA of a Binary Tree (LC.236)

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

Example

+ 4
 / \
3   7
   / \
  5   6
Input: LCA(3,5) Output: 4
Input: LCA(5,6) Output: 7
Input: LCA(6,7) Output: 7

Assume two nodes are in the tree.

Analysis

Obviously, traversing won't work well because we can't visit each node only once from top down. Now we have to come up with a task, the same task, for both the left subtree and the right subtree.

4 cases for the root:

1. LCA in is leftSubtrees

2. LCA is in rightSubtree

3. root is the LCA

4. LCA doesn't exist

If you can find LCA, return the LCA. If you can only find p/q, then return p/q.

base
if root == null
  return null
if root == A or root == B
  return root

divide
assign findLCA to leftsSubtree
assign findLCA to rightSubtree

conquer
4 cases for LCA
1. left != null && right != null then root is the LCA
2. left != null && right == null then left is the LCA
3. left == null && right != null then right is the LCA
4. LCA doesn't exist in this subtree

Problematic Code

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null)
        return null;
    if (root == p || root == q)
        return root;
    // divide
    TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
    TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);
    // conquer
    if (leftLCA != null && rightLCA != null) return root;
    if (leftLCA != null) return leftLCA;
    if (rightLCA != null) return rightLCA;
    return null;
}

This piece of code is problematic for several reasons. The first one is the way we define the state. The return type can be a LCA or a target node we have found. This will cause problems in the follow up question.

Follow up #1 (LI.578)

What if node1 or node2 might not exist in the tree? Return null in that case.

Analysis

Previous, the program will return node1 or node2 if the other does not exist in the tree. Now we need to distinguish these two cases. 1. node2 is a descendant of node1 2. node2 is not in the current tree

Examples Lesson

Always do a few examples (exhaust all cases) before talk about your approach.

Test Cases:

Case 1: node1 and node2 in the left subtree (CHECK)
we can't early terminate when root == node1 or root == node2
we need to travel all the way down
Case 2: node1 and node2 in the right subtree (CHECK)
Case 3: node1 in the left subtree, node2 in the right subtree (CHECK)
Case 4: node1 is the root, node2 in the right subtree (CHECK)
Case 5: node1 and node2 are the root (CHECK)
Case 6: node1 is the left subtree, node2 is in a separate tree (CHECK)

Approach

base
if root == null
    return (null, null)
// if root == node1 or root == node2

divide
left = lcaHelper(root.left, node1, node2)
right = lcaHelper(root.right, node1, node2)

merge
already found lca
if left.lca != null: return left
if right.lca != null: return right

the current root is the lca
if root == node1 && root == node2
    return (null, root)
if left.targetNode != null and right.targetNode != null
    return (null, root)
if root == node1 || root == node2
    if left.targetNode != null
        return (null, root)
    else if right.targetNode != null
        return (null, root)
    else
        return (root, null) // current root is a targetNode

the current root is not the lca pass along the info
if left.targetNode != null
    return left
else
    return right

Refined Code

private class LCAType {
    TreeNode targetNode;
    TreeNode lca;
    public LCAType(TreeNode node1, TreeNode lca) {
        targetNode = node1;
        this.lca = lca;
    }
}

public TreeNode lowestCommonAncestor3(TreeNode root, 
                                      TreeNode node1, 
                                      TreeNode node2) {
    LCAType result = lcaHelper(root, node1, node2);
    return result.lca;
}

private LCAType lcaHelper(TreeNode root, 
                          TreeNode node1, 
                          TreeNode node2) {
    // base
    if (root == null) {
        return new LCAType(null, null);
    }
    // divide
    LCAType left = lcaHelper(root.left, node1, node2);
    LCAType right = lcaHelper(root.right, node1, node2);
    // merge
    // already found lca
    if (left.lca != null) return left;
    if (right.lca != null) return right;
    // current root is lca
    if (root == node1 && root == node2) {
        return new LCAType(null, root);
    }
    if (left.targetNode != null && right.targetNode != null) {
        return new LCAType(null, root);
    }
    // current root is a target node
    if (root == node1 || root == node2) {
        if (left.targetNode != null || right.targetNode != null) {
            return new LCAType(null, root);
        } else {
            return new LCAType(root, null); 
        }
    }
    // current root is not a lca nor a target node, just pass along the info
    if (left.targetNode != null) return left;
    else return right;
}

Follwo Up #2 (LI.474)

Given parent pointers

Follow Up #3

Find all common ancestors. You can need to store the path to root in an array list. Then find intersection of two arrays.

References

• Finding the Lowest Common Ancestor by stoimen

• Crack the Coding Interview Ch4 Q7 Solution