Lowest Common Ancestor of a BST

Given a BST and two of its nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants (a node counts as its own descendant).

A way to picture it

Two friends live somewhere in a city laid out like a BST. You start at the town square. If both addresses are west, go west; if both are east, go east. The first corner where their directions split is where their routes last shared the road.

How to approach it

From the root: if p and q are both smaller, go left; both larger, go right. Otherwise the current node is the split point — the LCA.

Example

Input: {"root":[6,2,8,0,4,7,9,null,null,3,5],"p":2,"q":8}. Output: 6.

Complexity: O(h) time and O(1) space. One root-to-node walk, no recursion needed.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.