Language Selection
Choose your preferred programming language
Lowest Common Ancestor
Problem Statement
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “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).”
Examples
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.
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.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Explanation: The LCA of nodes 1 and 2 is 1.
Constraints
- The number of nodes in the tree is in the range
[2, 10^5]. -10^9 <= Node.val <= 10^9- All
Node.valare unique. p != qpandqwill exist in the tree.
Approach 1: Recursive DFS (Optimal)
Algorithm
Use recursion to find the lowest common ancestor by checking if nodes are in left or right subtrees.
Steps:
- Base case: if current node is null, return null
- If current node is p or q, return current node
- Recursively search left and right subtrees
- If both subtrees return non-null, current node is LCA
- Return non-null result from either subtree
Implementation
Python:
import sys
def lowestCommonAncestor(root, p, q):
"""
Find lowest common ancestor using recursive DFS
Time: O(n)
Space: O(h) where h is height of tree
"""
# Recursion depth equals tree height, up to 10^5 on a skewed tree
sys.setrecursionlimit(max(sys.getrecursionlimit(), 10**5 + 1000))
if not root:
return None
# If current node is p or q, return it
if root == p or root == q:
return root
# Search in left and right subtrees
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
# If both subtrees return non-null, current node is LCA
if left and right:
return root
# Return non-null result from either subtree
return left or right
Java:
import java.util.*;
class Solution {
/**
* Find lowest common ancestor using DFS with an explicit stack
* Time: O(n)
* Space: O(h) where h is height of tree
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// Explicit stack replaces the recursion: each frame holds a node and its stage
// (0 = not started, 1 = left subtree done, 2 = both subtrees done)
List<TreeNode> nodes = new ArrayList<>();
List<Integer> stages = new ArrayList<>();
List<TreeNode> results = new ArrayList<>(); // subtree results, may contain null
nodes.add(root);
stages.add(0);
while (!nodes.isEmpty()) {
int top = nodes.size() - 1;
TreeNode node = nodes.get(top);
int stage = stages.get(top);
if (stage == 0) {
// If current node is p or q, return it
if (node == p || node == q) {
nodes.remove(top);
stages.remove(top);
results.add(node);
continue;
}
// Search in left subtree
stages.set(top, 1);
if (node.left == null) {
results.add(null);
} else {
nodes.add(node.left);
stages.add(0);
}
} else if (stage == 1) {
// Search in right subtree
stages.set(top, 2);
if (node.right == null) {
results.add(null);
} else {
nodes.add(node.right);
stages.add(0);
}
} else {
nodes.remove(top);
stages.remove(top);
TreeNode right = results.remove(results.size() - 1);
TreeNode left = results.remove(results.size() - 1);
// If both subtrees return non-null, current node is LCA
if (left != null && right != null) {
results.add(node);
} else {
// Return non-null result from either subtree
results.add(left != null ? left : right);
}
}
}
return results.get(0);
}
}
Go:
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
/**
* Find lowest common ancestor using recursive DFS
* Time: O(n)
* Space: O(h) where h is height of tree
*/
if root == nil {
return nil
}
// If current node is p or q, return it
if root == p || root == q {
return root
}
// Search in left and right subtrees
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// If both subtrees return non-null, current node is LCA
if left != nil && right != nil {
return root
}
// Return non-null result from either subtree
if left != nil {
return left
}
return right
}
JavaScript:
/**
* Find lowest common ancestor using DFS with an explicit stack
* Time: O(n)
* Space: O(h) where h is height of tree
*/
function lowestCommonAncestor(root, p, q) {
if (!root) {
return null;
}
// Explicit stack replaces the recursion: each frame is [node, stage]
// (0 = not started, 1 = left subtree done, 2 = both subtrees done)
const stack = [[root, 0]];
const results = []; // subtree results, may contain null
while (stack.length > 0) {
const frame = stack[stack.length - 1];
const node = frame[0];
if (frame[1] === 0) {
// If current node is p or q, return it
if (node === p || node === q) {
stack.pop();
results.push(node);
continue;
}
// Search in left subtree
frame[1] = 1;
if (node.left) {
stack.push([node.left, 0]);
} else {
results.push(null);
}
} else if (frame[1] === 1) {
// Search in right subtree
frame[1] = 2;
if (node.right) {
stack.push([node.right, 0]);
} else {
results.push(null);
}
} else {
stack.pop();
const right = results.pop();
const left = results.pop();
// If both subtrees return non-null, current node is LCA
if (left && right) {
results.push(node);
} else {
// Return non-null result from either subtree
results.push(left || right);
}
}
}
return results[0];
}
C#:
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Find lowest common ancestor using DFS with an explicit stack
/// Time: O(n)
/// Space: O(h) where h is height of tree
/// </summary>
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// Explicit stack replaces the recursion: each frame holds a node and its stage
// (0 = not started, 1 = left subtree done, 2 = both subtrees done)
var nodes = new List<TreeNode> { root };
var stages = new List<int> { 0 };
var results = new List<TreeNode>(); // subtree results, may contain null
while (nodes.Count > 0) {
int top = nodes.Count - 1;
TreeNode node = nodes[top];
int stage = stages[top];
if (stage == 0) {
// If current node is p or q, return it
if (node == p || node == q) {
nodes.RemoveAt(top);
stages.RemoveAt(top);
results.Add(node);
continue;
}
// Search in left subtree
stages[top] = 1;
if (node.left == null) {
results.Add(null);
} else {
nodes.Add(node.left);
stages.Add(0);
}
} else if (stage == 1) {
// Search in right subtree
stages[top] = 2;
if (node.right == null) {
results.Add(null);
} else {
nodes.Add(node.right);
stages.Add(0);
}
} else {
nodes.RemoveAt(top);
stages.RemoveAt(top);
TreeNode right = results[results.Count - 1];
results.RemoveAt(results.Count - 1);
TreeNode left = results[results.Count - 1];
results.RemoveAt(results.Count - 1);
// If both subtrees return non-null, current node is LCA
if (left != null && right != null) {
results.Add(node);
} else {
// Return non-null result from either subtree
results.Add(left ?? right);
}
}
}
return results[0];
}
}
Complexity Analysis
- Time Complexity: O(n) - Visit each node exactly once
- Space Complexity: O(h) - Recursion stack depth equals tree height
Key Insights
- LCA Property: LCA is the lowest node that has both nodes as descendants
- Recursive Approach: Most elegant and efficient solution
- Path Finding: Alternative approach using path comparison
- Node Identity: Check node identity, not values
- Early Termination: Return as soon as LCA is found
Edge Cases
- One Node is Ancestor: One node is ancestor of the other
- Root is LCA: Root is the lowest common ancestor
- Same Node: Both nodes are the same (shouldn’t happen per constraints)
- Skewed Tree: Handle left-skewed or right-skewed trees
- Large Tree: Handle trees with many nodes
Test Cases
def test_lowestCommonAncestor():
# Test case 1: Normal case
root1 = TreeNode(3)
root1.left = TreeNode(5)
root1.right = TreeNode(1)
root1.left.left = TreeNode(6)
root1.left.right = TreeNode(2)
root1.right.left = TreeNode(0)
root1.right.right = TreeNode(8)
root1.left.right.left = TreeNode(7)
root1.left.right.right = TreeNode(4)
p1 = root1.left # 5
q1 = root1.right # 1
result1 = lowestCommonAncestor(root1, p1, q1)
assert result1 == root1 # 3
# Test case 2: One node is ancestor
p2 = root1.left # 5
q2 = root1.left.right.right # 4
result2 = lowestCommonAncestor(root1, p2, q2)
assert result2 == root1.left # 5
# Test case 3: Root is LCA
root3 = TreeNode(1)
root3.left = TreeNode(2)
p3 = root3 # 1
q3 = root3.left # 2
result3 = lowestCommonAncestor(root3, p3, q3)
assert result3 == root3 # 1
print("All tests passed!")
test_lowestCommonAncestor()
Follow-up Questions
- LCA in BST: Find LCA in binary search tree?
- LCA with Parent Pointers: Use parent pointers for optimization?
- LCA of Multiple Nodes: Find LCA of more than two nodes?
- LCA with Distance: Find LCA and distance to both nodes?
- LCA in N-ary Tree: Handle n-ary trees?
Common Mistakes
- Value Comparison: Comparing node values instead of node identity
- Missing Base Cases: Not handling null nodes properly
- Wrong Return Logic: Not handling the case where both subtrees return non-null
- Path Finding Errors: Incorrect path construction or comparison
- Edge Case Handling: Not handling one node being ancestor of the other
Interview Tips
- Start with Recursion: Most intuitive and efficient approach
- Explain LCA Concept: Show understanding of lowest common ancestor
- Handle Edge Cases: Mention one node being ancestor of the other
- Discuss Trade-offs: Compare recursive vs path finding approaches
- Follow-up Ready: Be prepared for BST and parent pointer variations
Concept Explanations
Lowest Common Ancestor: The LCA of two nodes is the lowest node in the tree that has both nodes as descendants. A node can be a descendant of itself.
Recursive Approach: We recursively search for both nodes in the left and right subtrees. If both subtrees return non-null results, the current node is the LCA. If only one subtree returns a non-null result, that result is the LCA.
Path Finding Approach: We find the path from root to each node, then compare the paths to find the last common node. This approach is more intuitive but less efficient.
Why Recursion Works: The problem has a recursive structure - if we can find the LCA in a subtree, we can determine the LCA for the entire tree.
Node Identity: We check node identity (reference equality) rather than node values, since nodes can have the same value but be different nodes.
Early Termination: The recursive approach can terminate early when it finds one of the target nodes, making it more efficient than the path finding approach.