Given a binary search tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as a descendant of itself, so if p is an ancestor of q, the answer is p. All values are unique and both nodes exist in the tree.
- 2 <= number of nodes <= 10^5
- -10^9 <= Node.val <= 10^9
- All values are unique
- p != q and both are in the tree
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The general binary tree solution searches both subtrees recursively in O(n). A BST gives us more: from any node we know exactly which side a value lives on. If both p and q are smaller than the current node, the answer is in the left subtree; if both are larger, it is in the right subtree. The first node where they go different ways (or where the node equals one of them) is the split point, and that is the lowest common ancestor.
Algorithm
- Start at
cur = root. - If
p.valandq.valare both less thancur.val, move tocur.left. - Else if both are greater than
cur.val, move tocur.right. - Otherwise
curseparates them (or equals one of them): returncur.
O(h), where h is the tree heightSpace: O(1) with the iterative loopp or q, and the node where both recursive calls return non-null is the answer.class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': cur = root while cur: if p.val < cur.val and q.val < cur.val: cur = cur.left # both on the left elif p.val > cur.val and q.val > cur.val: cur = cur.right # both on the right else: return cur # they split here return None