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.