The problem
A binary search tree (BST) keeps, at every node, smaller values in the left subtree and larger ones in the right.
Given a BST and two of its nodes, p and q, return their lowest common ancestor: the deepest node that has both of them below it (a node counts as below itself).
Examples
01
- Input
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
- Output
6
02
- Input
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
- Output
2
03
- Input
root = [2, 1], p = 2, q = 1
- Output
2
Constraints
- 2 ≤ number of nodes ≤ 10⁵
- −10⁹ ≤ Node.val ≤ 10⁹
- All values are different.
p≠q, and both are in the tree.
The idea
Start at the root. If both values are smaller than this node, both nodes are in its left subtree, so the answer is there too; if both are larger, it is on the right.
Otherwise they split here — one goes left and one right, or one of them is this very node — and no deeper node can have both below it. That node is the answer. Only one path is walked, and nothing is stored.
- Time
- O(h) — one path from the root
- Space
- O(1)
Solution · every language run against every case
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': node = root while node: if p.val < node.val and q.val < node.val: node = node.left # both are in the left subtree elif p.val > node.val and q.val > node.val: node = node.right # both are in the right subtree else: return node # they split here (or one of them is here)