We have a binary search tree and two nodes, p and q, that are guaranteed to exist in the tree. We need to find their lowest common ancestor, which is the deepest node in the tree that has both p and q somewhere in its subtree (including itself).

This is a BST, not just any binary tree. In a BST, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering lets us use node values to figure out where p and q sit relative to any node, instead of searching every branch.

If both p and q are smaller than the current node, their LCA must be in the left subtree. If both are larger, the LCA must be in the right subtree. The moment p and q split, meaning one goes left and the other goes right (or one of them equals the current node), the current node is the LCA. That split point is the deepest node that has both as descendants.

Key Constraints:

Intuition

Ignore the BST property for now and solve this as if it were a regular binary tree. Search for both nodes using DFS and let the recursion report where they meet.

For each node, recursively check the left and right subtrees. If p is found in one subtree and q in the other, the current node is the LCA. If both are found in the same subtree, the LCA is deeper in that subtree. If the current node itself is p or q, it qualifies as the LCA, since a node counts as its own descendant.

This works for any binary tree, not just BSTs, so it never uses the value ordering. That ordering is what the next two approaches exploit to avoid visiting both subtrees.

Algorithm

Visualization and Code

This approach visits both subtrees at every node, even though the BST ordering already determines which single direction to go. The next approach uses that ordering to navigate straight to the LCA.

Intuition

The BST ordering tells us where any value lives relative to the current node. For a node with value v, everything in the left subtree is less than v and everything in the right subtree is greater than v.

So if both p.val and q.val are less than the current node's value, both nodes are in the left subtree, and the LCA must be there too. If both are greater, the LCA is in the right subtree.

When p and q fall on different sides, or one of them equals the current node, the current node is the LCA. Searching further is unnecessary because p and q cannot share a deeper common ancestor: going one level deeper enters the subtree of only one of them.

Algorithm

Visualization and Code

This follows a single path down the tree, but it still uses O(h) space for the recursion stack. Because the recursion never combines results from two subtrees and never backtracks, it can be rewritten as a loop that uses constant space.

Intuition

Approach 2 recurses in a single direction at each step, with no backtracking and no combining of results. Replacing the recursion with a while loop removes the call stack, dropping the space cost from O(h) to O(1) while keeping the same logic.

A pointer walks down the tree: move left when both values are smaller, move right when both are larger, and stop when they split.

Algorithm

Visualization and Code