215. Lowest Common Ancestor of a Binary Search Tree
A binary search tree keeps its keys ordered: every value in a node's left subtree is smaller than the node, every value in its right subtree is larger. You receive the root of such a tree along with two of its nodes, p and q, and must return their lowest common ancestor — the deepest node whose subtree contains both of them.
A node counts as a member of its own subtree, so if q sits somewhere below p, the answer is p itself.
Your function is handed the actual TreeNode objects for p and q (the judge locates them by value first) and should return the ancestor node; the judge prints that node's value. All values in the tree are distinct, and both nodes are guaranteed to be present.
The generic binary-tree solution works here — but the ordering invariant lets you find the answer with a single downward walk and no memory at all.
Example 1:
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: 2 is smaller than the root 6 and 8 is larger, so their root-to-node paths part ways at 6 — no deeper node contains both.
Example 2:
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: 4 lives in 2's right subtree, and a node belongs to its own subtree — so 2 is the deepest node containing both.
Constraints:
- 2 ≤ number of nodes ≤ 10⁵
- -10⁹ ≤ node value ≤ 10⁹, and all values are distinct
- p ≠ q, and both values exist in the tree
- The tree is a valid binary search tree.
Hints:
Forget the BST for a second: the LCA is the last node shared by the root-to-p path and the root-to-q path. In a BST you can write down each path without searching — comparisons tell you which way to step.
Now skip the paths entirely. Standing at a node: if both p and q are smaller, the answer lies left; if both are larger, it lies right; the first time they straddle you (or one equals the node), you are standing on the LCA. That walk uses O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Expected output: 6