Given a binary search tree and two nodes p and q, find their lowest common ancestor, taking advantage of the BST's sorted-order property.
Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 < 6 < 8, so they split at the root — 6 is the LCA.
The number of nodes is in the range [2, 10^5]p and q both exist in the tree and are distinctUnlike a general binary tree, a BST's sorted structure tells you the LCA's direction directly from a single value comparison at each node — no need to search both subtrees.
If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it must be in the right subtree.
The first node where p and q 'split' (one is <=, the other is >=) is the LCA — you don't need to go any deeper once that happens.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode curr = root;
while (curr != null) {
if (p.val < curr.val && q.val < curr.val) {
curr = curr.left;
} else if (p.val > curr.val && q.val > curr.val) {
curr = curr.right;
} else {
return curr; // split point (or one of p/q IS curr) — this is the LCA
}
}
return null;
}Time: O(h) · Space: O(1) iterative