Lowest Common Ancestor of a Binary Search Tree

Problem

You are given the root of a binary search tree and two nodes p and q that are both in the tree. Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as its own ancestor, so if p is an ancestor of q, the answer is p.

The tree satisfies the usual BST property: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

• The tree has between 2 and 200,000 nodes and may be badly unbalanced.
• All node values are distinct.
• p != q, and both are nodes of the tree.

Examples

• root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 17], p = 10, q = 30 → 20. The two values lie on opposite sides of 20.
• Same tree, p = 10, q = 17 → 10. 17 is inside 10's subtree, so 10 is its own ancestor and the answer.
• root = [8, 3], p = 8, q = 3 → 8.

Hints

1. In a BST, what does comparing p.val and q.val to the current node's value tell you about which subtree(s) they live in?
2. If both values are smaller than the current node, can the current node be the lowest common ancestor?
3. Walk down from the root: go left while both are smaller, go right while both are larger, and stop at the first node where they split (or where one equals the node).