Shared Ancestor in a Search Tree
MediumTrees
Problem
A binary search tree of distinct values contains two different values p and q.
Return the value of their lowest shared ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if p is an ancestor of q, the answer is p.
Example 1
- Input:
- root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
- Output:
- 6
2 is on the left of 6 and 8 on the right, so the paths split at 6.
Example 2
- Input:
- root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
- Output:
- 2
4 is inside 2's subtree.
Constraints
- 2 ≤ number of nodes ≤ 10^5
- -10^9 ≤ node.val ≤ 10^9
- p ≠ q, and both are present in the tree.
Hint
Show the first hint
Compare p and q with the root. When can you be sure the answer is not the root?
Walkthrough
How to approach it
01Clarify before coding
- Do I get node references or values? Values, and I return a value.
- Can p be an ancestor of q? Yes, then p is the answer.
- Are both guaranteed to be present? Yes, so no existence check is needed.
02Brute force
Find the root-to-node path for p and for q, then walk both paths together until they diverge.
Cost: O(h) time but O(h) extra memory for the two paths, and twice the walking.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.