Lowest Common Ancestor of a Binary Search Tree
Part of Practice: Levels & BST Rules
You are given a binary search tree (BST) — a tree where every node's left subtree holds only smaller values and its right subtree only larger values — plus two nodes p and q that both exist in it. Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as an ancestor of itself, so if p is an ancestor of q, the answer is p.
All node values are unique, p ≠ q, and the tree has up to 100,000 nodes.
Examples
- Input:
- root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
- Output:
- 6
2 sits in the root's left subtree and 8 in its right, so they split at 6.
- 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, and a node is its own ancestor, so the answer is 2 itself.
- Input:
- root = [2,1], p = 2, q = 1
- Output:
- 2
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.