187. Lowest Common Ancestor of a Binary Search Tree

In a BST the LCA is the first node where p and q fall on opposite sides (or one equals the node). Walk down: go left if both are smaller, right if both are larger, else you're at the split point.

Use the BST ordering

Unlike a general tree, a BST lets you decide direction by comparing values — no full search needed. Starting at the root:

• If both p and q are less than the current node, the LCA is in the left subtree.
• If both are greater, it's in the right subtree.
• Otherwise the paths to p and q diverge here (one on each side, or the node itself is p/q) → this node is the LCA.

Walk-through

node = root
while node:
    if p.val < node.val and q.val < node.val: node = node.left
    elif p.val > node.val and q.val > node.val: node = node.right
    else: return node

Worked example

BST rooted at 6 with p=2, q=8: at root 6, 2 < 6 but 8 > 6 → they split → LCA = 6. For p=2, q=4: both < 6 → go left to 2; now 2 == node → LCA = 2.

Complexity

• Time: O(h) — one comparison per level.
• Space: O(1) iterative.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (p.val < node.val && q.val < node.val) {
                node = node.left;
            } else if (p.val > node.val && q.val > node.val) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }
}