LCA of BST LeetCode 235 Deep Dive

LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree — asks you to find the lowest common ancestor of two nodes p and q in a BST. The lowest common ancestor is defined as the deepest node in the tree that has both p and q as descendants, where a node is allowed to be a descendant of itself. Both p and q are guaranteed to exist in the tree.

The problem is a member of the LCA family on LeetCode. LeetCode 236 (LCA of Binary Tree) is the general version that works on any binary tree. LeetCode 235 is the BST-specific version, and the BST ordering property makes the solution dramatically simpler — you do not need to search both subtrees or use postorder traversal.

Understanding why the BST property simplifies the problem is the core insight. In a general binary tree, you must explore both children and bubble up the result, giving O(n) time. In a BST, the ordering tells you exactly which direction to go, giving O(h) time where h is the tree height — O(log n) for a balanced BST.

The key insight is that a BST has a strict ordering property: for any node, all values in the left subtree are smaller and all values in the right subtree are larger. This ordering lets you determine at each node which direction both p and q lie — without visiting any other nodes.

If both p.val and q.val are less than the current node value, then both p and q are in the left subtree. You can safely move left — the LCA cannot be in the right subtree or at the current node, because the current node is larger than both targets. Symmetrically, if both values are greater than the current node, both p and q are in the right subtree and you move right.

When p and q are on different sides of the current node — one smaller and one larger — or when one of them equals the current node value, you have found the split point. This node is the deepest ancestor that contains both p and q. Going any deeper would leave one of them behind in the subtree you just came from.

The algorithm starts at the root and uses value comparison to navigate the tree. At each node, compare both p.val and q.val against the current node value. The comparison determines whether to move left, move right, or return the current node as the LCA. The loop or recursion terminates when the split point is found.

The split condition has three cases: if p.val < node.val and q.val > node.val (or vice versa), the current node is the split point and is the LCA. If p.val == node.val, then p is the current node, so p is an ancestor of q (or equals q), making p the LCA. If q.val == node.val, the symmetric argument applies and q is the LCA.

The iterative version uses a while loop with a current pointer starting at root. Each iteration either moves current to current.left or current.right, or returns current. The loop always terminates because p and q are guaranteed to exist in the tree — the split point is always found.

When you arrive at a node where p and q are on different sides, that node is the lowest common ancestor because it is the deepest node in the tree that still has both p and q in its subtree. Any node deeper than this split point would have both p and q on the same side — either both in its left subtree or both in its right — meaning the split has not yet happened. The split point is exactly where the paths to p and q diverge.

Going deeper past the split point would lose one of the nodes. If you move left past the split, q (which is in the right subtree) is no longer reachable from the current node. If you move right past the split, p is no longer reachable. So the split point is the deepest node that is still an ancestor of both p and q — which is the definition of the LCA.

A node being its own ancestor is handled naturally. If you reach a node whose value equals p.val, then the current node IS p, and since q is guaranteed to be in the tree and both p and q were reachable from all ancestors above this point, p must be an ancestor of q (or equal to q). Therefore p is the LCA. The same argument applies when the current node equals q.

The iterative approach uses a while loop and a current pointer. It is O(h) time and O(1) space — no call stack is used. The loop runs at most h iterations where h is the tree height. For a balanced BST this is O(log n); for a degenerate (linked-list-like) BST it is O(n). The iterative version is preferred in interviews because it is simple, space-efficient, and easy to trace.

The recursive approach applies the same three-way comparison: if both values are smaller, recurse left; if both are larger, recurse right; otherwise return current. It is O(h) time but O(h) space due to the call stack. For a balanced BST the stack depth is O(log n); for a degenerate BST it is O(n). The recursive version reads cleanly but the extra space is unnecessary given how simple the iterative loop is.

Choose the iterative version for interviews. It avoids stack overflow on degenerate inputs, uses O(1) space, and the while loop directly mirrors the algorithm description. The recursive version is useful for understanding the recursive decomposition of the BST, but adds no benefit over the iterative approach for this specific problem.

Python iterative version: def lowestCommonAncestor(root, p, q): current = root; while current: if p.val < current.val and q.val < current.val: current = current.left; elif p.val > current.val and q.val > current.val: current = current.right; else: return current. Five lines, O(h) time O(1) space. The while loop runs until the split is found — guaranteed to terminate because p and q exist in the tree.

Java iterative version: public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode current = root; while (current != null) { if (p.val < current.val && q.val < current.val) { current = current.left; } else if (p.val > current.val && q.val > current.val) { current = current.right; } else { return current; } } return null; }. Same O(h) time O(1) space. The return null at the end is unreachable given the problem guarantees.

Compare with LeetCode 236 (general binary tree LCA) which requires O(n) time postorder traversal: def lca(node): if not node or node == p or node == q: return node; left = lca(node.left); right = lca(node.right); return node if left and right else left or right. The BST version (LeetCode 235) skips all of this by using value comparison to prune the search.

LCA of Binary Tree (LeetCode 236) is the general version of this problem. It works on any binary tree, not just a BST, so it cannot use value comparison to prune the search. Instead it uses postorder traversal: recurse into both children, then return the current node if both children returned non-null results (meaning p and q are on different sides), or return whichever child returned non-null (meaning both p and q are in that subtree). This gives O(n) time and O(h) space.

Validate BST (LeetCode 98) and Kth Smallest Element in a BST (LeetCode 230) are companion problems that deepen your understanding of BST structure. Validate BST tests whether the BST ordering property holds throughout the tree — a prerequisite for algorithms like LCA of BST that rely on that ordering. Kth Smallest uses inorder traversal of the BST (which visits nodes in sorted order) to find the kth element in O(h + k) time.

The BST family of problems — LCA, insertion, deletion, search, validation, and traversal — all leverage the ordering property in different ways. Recognizing which BST property applies to each problem is the key skill. For LCA, it is the split-point observation. For search and insertion it is the same left-right navigation. For validation it is the invariant that every node must satisfy strict bounds inherited from its ancestors.