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: 7Assume 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:
LCA in is leftSubtrees
LCA is in rightSubtree
root is the LCA
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 subtreeProblematic 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 rightRefined 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
Last updated