Lowest Common Ancestor of a Binary Search Tree
Asked at Atlassian
Problem
Given a BST and two nodes p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that has both p and q as descendants. The BST property (left < root < right) lets you solve this in O(h) time without comparing every node.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Key insight: in a BST, if both p and q are less than root, the LCA must be in the left subtree. If both are greater, the LCA is in the right subtree. If they split (one smaller, one larger, or one equals root), the current root is the LCA.
Visual walkthrough: BST with root=6, p=2, q=8.
6
/
2 8
- At root 6: p=2 < 6 and q=8 > 6. They split! LCA = 6.
- No need to recurse further.
Another example: root=6, p=2, q=4.
6
/
2 8
4
- At root 6: both 2 and 4 < 6, go left.
- At node 2: p=2 equals current. Since p is an ancestor of q, LCA = 2.
The recursive approach: start at root. If both p and q < root, recurse left. If both > root, recurse right. Otherwise (split or one equals root), return current node.
Iterative approach: same logic but use a while loop. Start at root, move left or right based on comparisons. When you reach a split point (or one of the values), that's your LCA. Saves stack space.
Time: O(h) where h is the tree height. For a balanced BST, h = log(n). For a skewed BST, h = n. Space: O(1) iterative, O(h) recursive.
Optimal Approach
Start at root. Compare p and q values with the current node:
- If both p and q are less than the current node, the LCA is in the left subtree. Move to left child.
- If both p and q are greater than the current node, the LCA is in the right subtree. Move to right child.
- Otherwise (one is less, one is greater, or one equals current), the current node is the LCA. Return it.
Walkthrough: BST = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8.
- Current = 6: 2 < 6 and 8 > 6. Split. Return 6.
Walkthrough: BST same, p = 2, q = 4.
- Current = 6: 2 < 6 and 4 < 6. Both left. Go left to 2.
- Current = 2: p equals current. Return 2.
Time: O(h). Space: O(1) iterative.
What Trips People Up in Real Interviews
Assuming you need to traverse the entire tree. The BST property means you can prune half the tree at each step. Don't do a full DFS unless the interviewer specifically says the tree is NOT a BST.
Confusing LCA with lowest common node in value. The LCA is defined by structure (the deepest node that is an ancestor of both), not by value comparison. A node can be its own ancestor in this definition.
Forgetting that p or q might be ancestors of each other. If p=2 and q=4, and 2 is an ancestor of 4 in the tree, the LCA is 2 itself. Your code handles this naturally because the split condition catches it.
Trying to find paths and then comparing. You don't need to store full paths. The BST property gives you the answer directly through comparisons at each node. Path storage is O(n) space for no benefit.
Handling the case where p equals q. If p == q, the LCA is p (or q). Your code handles this because at the node equal to p, the split condition triggers immediately.
Solution Code
def lowestCommonAncestor(root, p, q):
curr = root
while curr:
if p.val < curr.val and q.val < curr.val:
curr = curr.left
elif p.val > curr.val and q.val > curr.val:
curr = curr.right
else:
return currFrequently Asked Questions
What is the Lowest Common Ancestor of a Binary Search Tree problem?
Given a BST and two nodes p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that has both p and q as descendants. The BST property (left < root < right) lets you solve this in `O(h)` time without comparing every node.
How do you solve Lowest Common Ancestor of a Binary Search Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Lowest Common Ancestor of a Binary Search Tree?
Lowest Common Ancestor of a Binary Search Tree is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Lowest Common Ancestor of a Binary Search Tree?
- Assuming you need to traverse the entire tree. The BST property means you can prune half the tree at each step. Don't do a full DFS unless the interviewer specifically says the tree is NOT a BST.
- Confusing LCA with lowest common node in value. The LCA is defined by structure (the deepest node that is an ancestor of both), not by value comparison. A node can be its own ancestor in this definition.
- Forgetting that p or q might be ancestors of each other. If p=2 and q=4, and 2 is an ancestor of 4 in the tree, the LCA is 2 itself. Your code handles this naturally because the split condition catches it.
- Trying to find paths and then comparing. You don't need to store full paths. The BST property gives you the answer directly through comparisons at each node. Path storage is `O(n)` space for no benefit.
- Handling the case where p equals q. If p == q, the LCA is p (or q). Your code handles this because at the node equal to p, the split condition triggers immediately.