Lowest Common Ancestor

This is classic problem of binary tree. We'll discuss the original LCA and some of the variations. It is practical in the DOM tree. The question can be framed as given a family tree and two persons, determine if they have blood relationship.

*** This post needs to be reorganized

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

Analysis

Try D&C first.
4 cases for the boss root:

1. LCA in is leftSubtrees
2. LCA is in rightSubtree
3. root is the LCA
4. LCA doesn't exist

But then we get kinda stuck. Not exactly sure what to return. This the time that you ask for clarifications (before you write code).

If you can find LCA, return the LCA. If you can only find p/q, then return p/q. If neither can be found, return null.

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

We assume p and q exist in the tree. This approach will not work if they are not guaranteed to be in the tree.

"Elegant" Code

This is bad solution because it combines two cases into one with root == p || root == q

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

Follow up #1 (LC.578)

What if p or q might not exist in the tree? Return null if LCA does not exist (instead of p or q).

Analysis

We'll need a structure to hold LCA, p and q.

Lesson

private class ReturnType {
    TreeNode LCA, targetA, targetB;
    ReturnType (TreeNode root, TreeNode A, TreeNode B) {
        LCA = root;
        targetA = A;
        targetB = B;
    }
}

public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
    ReturnType result = helper(root, A, B);
    if (result.LCA != null) {
        return result.LCA;
    } else if ((result.targetA != null && root == B) || (result.targetB != null && root == A)) {
        return root;
    } else {
        return null;
    }
}

private ReturnType helper(TreeNode root, TreeNode A, TreeNode B) {
    // base
    if (root == null) {
        //System.out.println("p1: " + root.val);
        return new ReturnType(null, null, null);
    }
    if (root == A) {
        TreeNode B2 = leftSubtree.targetB == null ? rightSubtree.targetB : leftSubtree.targetB;
        //System.out.println("p2: " + root.val);
        return new ReturnType(null, A, B2);

    }
    if (root == B) {
        TreeNode A2 = leftSubtree.targetA == null ? rightSubtree.targetA : leftSubtree.targetA;
        //System.out.println("p3: " + root.val);
        return new ReturnType(null, A2, B);
    }

    // divide
    ReturnType leftSubtree = helper(root.left, A, B);
    ReturnType rightSubtree = helper(root.right, A, B);

    // conquer
    if (leftSubtree.LCA != null)
        return leftSubtree;
    else if (rightSubtree.LCA != null)
        return rightSubtree;
    else if (leftSubtree.targetA != null && rightSubtree.targetB != null)
        return new ReturnType(root, leftSubtree.targetA, rightSubtree.targetB);
    else if (leftSubtree.targetB != null && rightSubtree.targetA != null)
        return new ReturnType(root, rightSubtree.targetA, leftSubtree.targetB);
    else if (leftSubtree.targetA != null || leftSubtree.targetB != null)
        return leftSubtree;
    else
        return rightSubtree;
}

This is what happens when you skim through the question, skip doing examples and write code without a clear understanding the of the problem. READ READ READ the question. Before you do anything.

Real Analysis

A or B might not be in the tree. How do we handle that?

Real Code

Investigate:

1. why {1}, 1, 1 is a valid case for LCA?
2. how to handle {1, 2}, 1, 2 without doing the explicit check ( I guess we have to since it's a special case).
3. give a clear thought process on divide and conquer
4. Comparing with the sample solutions to see what can you improve here

private class ReturnType {
    TreeNode LCA;
    TreeNode nodeAB;
    ReturnType(TreeNode LCA, TreeNode node) {
        this.LCA = LCA;
        nodeAB = node;
    }
}

public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
    if (root == A && root == B)
        return root;
    else
        return helper(root, A, B).LCA;
}

private ReturnType helper(TreeNode root, TreeNode A, TreeNode B) {
    // base case
    if (root == null) {
        return new ReturnType(null, null);
    }

    // divide
    ReturnType leftSubtree = helper(root.left, A, B);
    ReturnType rightSubtree = helper(root.right, A, B);

    // bug fix where root can be nodeAB and LCA
    if ( (leftSubtree.nodeAB != null || rightSubtree.nodeAB != null) 
         && (root == A || root == B) ) {
        return new ReturnType(root, null);
    }

    if (root == A || root == B) {
        return new ReturnType(null, root);
    }

    // conquer
    if (leftSubtree.nodeAB != null && rightSubtree.nodeAB != null) {
        return new ReturnType(root, null);
    } else if (leftSubtree.LCA != null || leftSubtree.nodeAB != null) {
        return leftSubtree;
    } else if (rightSubtree.LCA != null || rightSubtree.nodeAB != null) {
        return rightSubtree;
    } else {
        return new ReturnType(null, null);
    }
}

Follow up #2

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

LCA of 2 nodes in a Binary Tree by by Saurabh Kumar