Lowest Common Ancestor
This post will be about Lowest Common Ancestor for Binary Tree
There are multiple variations of this problem.
- 236. Lowest Common Ancestor of a Binary Tree
- 1644. Lowest Common Ancestor of a Binary Tree II
- 1676. Lowest Common Ancestor of a Binary Tree IV
Assumptions: You know what LCA means.
236. LCA of binary tree
We will first start with finding LCA of two nodes in a given. In this case, it is specified in the problem that 2 nodes will exist in the tree.
Problem Statment :
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Intution
There are three possible scenarios in this:
- Case 1: A node can have p in left and right in q (or vice versa)
- Case 2: A node can be p and have left in q
- Case 3: A node can be q and have right in p
How to write recursion:
- Base Case
- Hypothesis
- Induction
Base Case
- This case here is the least valid input, which will be a node becoming null.
Hypothesis
- Assume that we already have answers from left and right subtree.(Just trust me on this and make this assumption
left = lca(node.left)
right = lca(node.right)Induction
// if the current node is either p or q, case 1
if(node == p || node == q)
return node
// if we got answers from both left and right. It means we have found either p or q in both parts of subtree.
// Since we are doing dfs approach, which means going in depth first, this node would be the LOWEST common ancestor
if(left != null && right != null)
return node;
// if we have found answer in left, then that would be LCA. Refer to Case 2 above
if( left != null)
return left;
//Similarly for right, Case 3
if(right != null)
return right;Optimization:
One optimization we can do for above is, we can check if we have already found the node before checking left and right subtree.
Thus, the full code is as follows:
TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
//Base case
if(node == null)
return node;
if(node == p || node == q)
return node;
TreeNode left = lca(node.left, p, q);
TreeNode right = lca(node.right, p, q);
if(left != null && right!= null)
return node;
if(left != null)
return left;
if(right != null)
return right
}1644. Lowest Common Ancestor of a Binary Tree II
Lets change the constraint of above question where p and q may not exist in Binary Tree. In that case we need to return null.
For this variation, the above logic will return wrong answer since we are checking that if we found either p or q and based on that returning the current value
if(node == p || node == q)
return node;Basically, what we were doing was as soon as we either either of them, we were returning.
But for this variation, we need to check for both. This means we need to keep on checking till we have found either both or have traversed full tree.
Approach
- Maintain a state for each p and q
TreeNode longestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int[] lca = new lca[2];
TreeNode ans = lca(node, p, q, lca);
return lca[0] + lca[1] == 2 ? ans : null;
}
TreeNode lca(TreeNode node, TreeNode p, TreeNode q, int[] lca) {
//Base case
if(node == null)
return node;
TreeNode left = lca(node.left, p, q);
TreeNode right = lca(node.right, p, q);
if(node == p) {
lca[0] = 1;
return node;
}
if(node ==q) {
lca[1] = 1;
return node;
}
if(left != null && right!= null)
return node;
if(left != null)
return left;
if(right != null)
return right;
}1676. Lowest Common Ancestor of a Binary Tree IV
In this variation, we are passed a list of nodes instead of p and q and they all exists in tree
Constraints:
The number of nodes in the tree is in the range [1, 104].
-109 <= Node.val <= 109
All Node.val are unique.
All nodes[i] will exist in the tree.
All nodes[i] are distinct.
Variation:
- We just need to change the logic of p and q checks.
//Condition- nodes are present in tree
TreeNode lca(TreeNode root, TreeNode[] nodes) {
if( root == null)
return root;
// Main variation for this case
for(TreeNode n : nodes)
if(n == root)
return root;
TreeNode left = lca(root.left, nodes);
TreeNode right = lca(root.right, nodes);
if( left != null && right != null)
return root;
if(left!= null)
return left;
else
return right;
}Bonus: What if there is new contraint where a node might not exist in the tree
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
TreeNode[] ans = new TreeNode[1];
ans[0] = null;
int count = lca(root, set, ans);
return ans[0];
}
int lca(TreeNode node, Set<Integer> set, TreeNode[] ans) {
int matched = 0;
if(node == null)
return 0;
int left = lca(node.left, set, ans);
int right = lca(node.right, set, ans);
matched += (set.contains(node.val)) ? 1 : 0;
matched += left + right;
// we need to check if ans[0] is not null
if( matched == set.size() && ans[0] == null) {
ans[0] = node;
}
return matched;
}