The problem
In a binary search tree (smaller values on the left, bigger on the right), find the lowest common ancestor of two nodes p and q: the deepest node that has both of them below it (a node counts as below itself).
Input: tree [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 5 Output: 4
Picture it
Picture a family tree where you’re looking for where two relatives’ family lines split. Start at the top. If both p and q are smaller than the current person, both live on the left side, so go left. If both are bigger, go right. As soon as they fall on different sides (or one of them is the current person), this is where their lines split.
How to recognise it
- The tree is a binary search tree (BST): smaller values on the left, bigger on the right, at every node.
- The question is about where two values' paths from the root split: the lowest node with both values below it (a node counts as below itself).
- In a BST, comparing a value with a node tells you which side it is on, without searching. That means you can walk down one path.
- Up to 10^5 nodes, so avoid visiting them all when the order already points the way.
Start with brute force
Ignore the ordering and use the general method for any binary tree: search both subtrees, and the node where p and q come back from different sides is the answer.
def lca_general(root, p, q): # ignores the BST order
if not root or root.val in (p, q):
return root
left = lca_general(root.left, p, q)
right = lca_general(root.right, p, q)
if left and right:
return root
return left or right
It is correct, but it may visit every node: O(n) time, about 10^5 steps here, and O(h) recursion space, where h is the height. A chain of 10^5 nodes would also overflow Python's default recursion limit of about 1,000 frames.
From brute force to the idea
- Find the waste. The general method searches both sides because it cannot know where p and q are. In a BST it can.
- Compare with the current node. If both values are smaller than
node.val, both are in the left subtree, so their lowest common ancestor is too: go left. If both are bigger, go right. - Recognise the split. Otherwise, one is on each side, or one of them equals
node.val. In both cases no deeper node has both below it, so this node is the answer. - No recursion needed. Each step moves one level down, so a simple
whileloop does it.
This is the key idea: walk down from the root while both values lie on the same side; the first node where they do not is the lowest common ancestor.
The shown code takes p and q as values. On LeetCode they are nodes, so compare p.val and q.val instead.
The key idea
Use the BST ordering: walk down while p and q are on the same side. O(height).
Python solution
def lca(root, p, q):
node = root
while node:
if p < node.val and q < node.val:
node = node.left # both are smaller: go left
elif p > node.val and q > node.val:
node = node.right # both are bigger: go right
else:
return node # they split hereIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (general tree method) | O(n): may visit every node | O(h): recursion stack |
| BST walk (shown code) | O(h): one step per level, about 17 for a balanced tree of 10^5 nodes, up to n for a chain | O(1): a single pointer |
Edge cases
- One value is an ancestor of the other (
p = 2,q = 4in[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]): returns 2, because at node 2pequals the node value. - p and q in either order:
(3, 5)and(5, 3)both return 4; the conditions are symmetric. - p equals q: returns that node.
- A value not in the tree: the code does not check.
lca(tree, 3, 100)returns 6, a node that only marks where the search paths split. LeetCode guarantees both exist. - Both values missing on the same side (say −5 and −1): the walk falls off the tree and returns
None. - Very deep tree: the loop has no recursion, so a 10^5-node chain is fine.
Common mistakes
- Using
<=or>=in the "go left" or "go right" test, which walks past the node when it equals p or q. - Forgetting that the tree is a BST and solving the general problem: correct, but it misses the point and costs O(n).
- Comparing node objects with numbers when LeetCode passes nodes: use
p.val.
In the same BST, return the number of edges on the path between the nodes holding p and q (both exist). For p = 0, q = 9 in [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] the answer is 4. Describe your approach, then write it if you like.
Compare with our answer
The path goes up from p to the split node and down to q. So find the split with the same walk, then count the steps from the split down to each value, again steering by comparison.
def distance(root, p, q):
split = lca(root, p, q)
def down(node, target):
steps = 0
while node.val != target:
node = node.left if target < node.val else node.right
steps += 1
return steps
return down(split, p) + down(split, q)
Time O(h), space O(1). When p equals q the answer is 0.
A strong answer mentions: that the path must pass through the lowest common ancestor, counting edges (not nodes) on each side, and that both searches use the BST order.
1. A sorted file-system index is stored as a BST of paths. You need the deepest entry under which two given paths both fall. Which approach fits best?
The BST order tells you which side each value is on, so one walk down of O(h) steps finds the split. Collecting paths or searching both sides works but ignores the order and costs more.
2. Why does the shown solution use O(1) extra space?
Each step replaces node with one child, so only one pointer is kept. A recursive version would use O(h) stack space, because Python does not reuse frames.
3. A learner writes if p <= node.val and q <= node.val: in the first test. Which query in [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] is now wrong?
At node 2, both 2 ≤ 2 and 0 ≤ 2 hold, so the walk goes left to 0 and returns 0. In the other queries, the walk never reaches a node equal to p or q while the other value is smaller, so it ends at the same node.
Score 60% or more and the lesson is marked complete.