Given the root of a binary search tree and two values p and q that both exist in it, return the VALUE of their lowest common ancestor — the deepest node that has both among its descendants, where a node counts as its own descendant. (The classic passes node references; values carry the same problem here, since a BST's values are unique.)
Examples
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: an ancestor may be one of the two nodes itself.
Example 3:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 5
Output: 4
Example 4:
Input: root = [2,1], p = 2, q = 1
Output: 2
Constraints
2 <= number of nodes <= 10^4
-10^9 <= Node.val <= 10^9, all values unique
p and q are values present in the tree, p != q
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. Walk Until the Values Split Optimal
Intuition
In a search tree the values themselves say which way to go. While both targets are smaller than the current node, the ancestor must be left; while both are larger, right. The first node where they disagree — or that equals one of them — is the deepest node with both below it. No recursion, no parent pointers, and no general-tree LCA algorithm: the ordering is the whole answer.
Algorithm
1. Start at the root. 2. Both values smaller: go left. 3. Both values larger: go right. 4. Anything else: this node is the lowest common ancestor.