LeetCode 235 Lowest Common Ancestor of BST - Example and Complexity Analysis

Find LCA of p = 2 and q = 8 in the BST rooted at 6.

At node 6: p = 2 < 6 and q = 8 > 6. Split! Node 6 is the LCA.

Find LCA of p = 2 and q = 4:

At node 6: both 2 and 4 < 6. Go left.

At node 2: p = 2 equals current. q = 4 > 2. Split! Node 2 is the LCA.

Find LCA of p = 0 and q = 4:

At node 6: both < 6. Go left.

At node 2: p = 0 < 2 and q = 4 > 2. Split! Node 2 is the LCA.

Single path from root to LCA. $O(h)$ time where $h$ is tree height. $O(1)$ space with iteration (or $O(h)$ with recursion).