What is the Lowest Common Ancestor (LCA) Problem?
Learn what the lowest common ancestor problem is, how to solve it in a binary tree and BST, and how to explain it in interviews.
Expected Interview Answer
The lowest common ancestor problem asks for the deepest node in a tree that has both of two given nodes as descendants, and it is typically solved in O(n) with a single recursive traversal, or in O(log n) per query after O(n log n) preprocessing when many queries are expected.
In a general binary tree, the standard recursive approach searches both subtrees for the two target nodes: if a node's left and right subtrees each report finding one target, that node itself is the LCA; otherwise the LCA is wherever a non-null result bubbles up from. In a binary search tree, this simplifies further since the LCA is the first node where the two target values diverge to different sides, letting you skip the general search entirely. When the same tree faces many repeated LCA queries, it pays to preprocess with binary lifting, storing each node's 2^k-th ancestor so any query jumps both nodes up to equal depth then binary-searches upward for the meeting point in O(log n). Euler tour plus sparse table is another common O(n log n) preprocessing, O(1) query approach for competitive settings.
- O(n) single-pass solution for a one-off query
- O(log n) per query after O(n log n) preprocessing for repeated queries
- Simplifies to a value-comparison walk in a binary search tree
- Foundational for tree-distance and ancestor-based algorithms
AI Mentor Explanation
Finding the LCA is like tracing two players' team histories back through a merger family tree of clubs to find the earliest shared parent club both eventually descended from. You walk each player's lineage of club splits and mergers upward and look for the first point where both lineages converge on the same ancestor club. If you needed to answer this for thousands of player pairs across the same club tree, you would pre-map each club's ancestors at doubling distances so any pair's common root is found by jumping upward in big strides instead of one step at a time. The deepest shared ancestor club is the answer, not just any shared ancestor further up.
Step-by-Step Explanation
Step 1
Recurse into both subtrees
From the current node, recursively search the left and right subtrees for the two target nodes.
Step 2
Check the split condition
If one target is found in each subtree, the current node is the LCA.
Step 3
Bubble up otherwise
If only one subtree returns a non-null result, propagate that result upward as the current best answer.
Step 4
Optimize for repeated queries
Precompute binary-lifting ancestor tables to answer each future LCA query in O(log n) instead of O(n).
What Interviewer Expects
- State the O(n) recursive approach for a single query on a general tree
- Simplify correctly for a binary search tree using value comparisons
- Mention binary lifting or Euler tour + sparse table for repeated queries
- Correctly identify that the LCA is the deepest, not just any, common ancestor
Common Mistakes
- Assuming the root is always a valid enough answer instead of the deepest common ancestor
- Forgetting the BST-specific optimization and always using the general O(n) approach
- Not considering repeated-query optimization when the interviewer hints at many queries
- Confusing LCA with the diameter or depth of the tree
Best Answer (HR Friendly)
“The lowest common ancestor problem is about finding the deepest node in a tree that is a parent of both of two given nodes. For a one-off search I would recurse through the tree once, but if I know I will be answering this many times on the same tree, I would preprocess it so each query becomes very fast.”
Code Example
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root, p, q):
if root is None or root is p or root is q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else rightFollow-up Questions
- How does the LCA algorithm simplify for a binary search tree?
- How would you answer many LCA queries efficiently on the same static tree?
- How would you compute the LCA if nodes only have parent pointers, not child pointers?
- How is LCA used to compute the distance between two nodes in a tree?
MCQ Practice
1. What is the time complexity of the standard recursive LCA algorithm for one query on a tree with n nodes?
The recursive approach visits every node in the worst case, giving O(n) time for a single query.
2. In a binary search tree, how can the LCA of two nodes be found more efficiently than the general tree approach?
BST ordering means the LCA is the first node where the two values split to different sides, avoiding full recursion.
3. Which technique allows answering many LCA queries on the same tree in O(log n) each?
Binary lifting precomputes 2^k ancestors per node, letting each query jump upward in O(log n) instead of O(n).
Flash Cards
What does the LCA of two nodes represent? — The deepest node in the tree that is an ancestor of both nodes.
What is the time complexity of a single general-tree LCA query? — O(n), via one recursive traversal.
How does the LCA algorithm simplify for a BST? — The LCA is the first node where the two target values diverge to different sides.
What technique speeds up repeated LCA queries on a static tree? — Binary lifting, giving O(log n) per query after O(n log n) preprocessing.