Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
according to the LCA definition.
Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.
Analysis
Recursive
The node which is the lowest common ancestor will have paths to both two given nodes, thus we can return the targeted node if we find them in the traversal. And return the node itself when both its left and right child tree return non-null node, which means it's the LCA node itself, or, return the non-null node from either left or right of its child.
Iterative
To find the lowest common ancestor, we need to find where is p and q and a way to track their ancestors. A parent pointer for each node found is good for the job. After we found both p and q, we create a set of p's ancestors . Then we travel through q 's ancestors , the first one appears in p 's is our answer.
Goal: given the root, find LCA ==> see root.left & root.right, having LCA or not ==> Then get answer on root
Divide
==> given the root's left-subtree, find LCA; If LCA == null, see if meets one of two nodes. If yes, return it
==> given the root's right-subtree, find LCA; If LCA == null, return the node if meets it.
Conquer - four cases
1. left != null && right != null ==> A, B is in different subtree ==> LCA = root
2. left != null && right == null ==> LCA is in the left-subtree, return left
3. left == null && right != null ==> LCA is in the right-subtree, return right
4. left == null && right == null ==> LCA is in neither left & right subtree, return null
Solution
Recursive
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor (root.left, p, q);
TreeNode right = lowestCommonAncestor (root.right, p, q);
return left == null ? right : right == null ? left : root;
}
}
*Favorite
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left != null ? left : right;
}
}
Verbose Recursion - (Most Easy to Understand Though)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (p.val == root.val || q.val == root.val) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
Iterative - using parent pointers
If we have parent pointers for each node we can traverse back from p and q to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parent.put(root, null);
stack.push(root);
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
}
Iterative - with comments
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Stack for tree traversal
Deque<TreeNode> stack = new ArrayDeque<>();
// HashMap for parent pointers
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
stack.push(root);
// Iterate until we find both the nodes p and q
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
// While traversing the tree, keep saving the parent pointers.
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
// Ancestors set() for node p.
Set<TreeNode> ancestors = new HashSet<>();
// Process all ancestors for node p using parent pointers.
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
// The first ancestor of q which appears in
// p's ancestor set() is their lowest common ancestor.
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
}