DSA problem
Lowest Common Ancestor of a Binary Search Tree
Given the root of a binary search tree and two nodes p and q that are guaranteed to exist in the tree, return their lowest common ancestor (LCA). The LCA is defined as the lowest node in the tree that has both p and q as descendants, where a node is allowed to be a descendant of itself.
In a general binary tree, finding the LCA requires a full O(n) DFS to discover paths from the root to each target. A BST gives away much more information through its ordering invariant: every comparison of the current node's value with p.val and q.val immediately tells you whether both targets are below-left, below-right, or split across the current node.
If both p.val and q.val are less than node.val, the LCA lies in the left subtree. If both are greater, it lies in the right subtree. The first time the targets straddle the current node — one less than or equal to node.val and the other greater than or equal — the current node is the LCA, because any deeper node would lose one of the two targets to the wrong side.
The optimal solution walks a single pointer down from the root, repeatedly applying these comparisons until a split point is found. It runs in O(h) time and O(1) extra space — strictly better than the generic binary-tree LCA algorithm.
Examples
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 42root = [2,1], p = 2, q = 12Constraints
- The number of nodes in the tree is in the range [2, 10^5].
- -10^9 <= Node.val <= 10^9
- All Node.val are unique.
- p != q
- Both p and q exist in the BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.