Lowest Common Ancestor of a BST

Problem

Given the root of a binary search tree and two nodes p and q known to exist in it, find their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node counts as a descendant of itself). (LeetCode 235.)

Examples

      6
     / \
    2   8
   / \  / \
  0  4 7   9
    / \
   3   5

Constraints

2 ≤ n ≤ 10⁵ nodes · all values unique · p and q both exist and are distinct

Attempt it first

This is the same question as Module 17's Lowest Common Ancestor of a Binary Tree, but with one extra fact available: the BST ordering invariant. That problem needed to search BOTH subtrees at every node, because a general binary tree gives no way to predict which side p and q are on. Before opening anything, work out what the BST invariant lets you conclude, from a single comparison at the current node, about which side (or whether this node itself) the LCA must be on — without recursing into both sides to find out.