Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree

What is this problem about?

The Lowest Common Ancestor (LCA) of a Binary Search Tree (BST) problem provides a BST and two target nodes, p and q. Your objective is to find their lowest common ancestor—the deepest node in the tree that has both p and q as descendants. A node is allowed to be a descendant of itself.

Why is this asked in interviews?

This is one of the most fundamental tree questions asked in tech interviews. It serves as a rapid screener to verify that a candidate actually understands the defining property of a Binary Search Tree: left children are strictly smaller than the parent, and right children are strictly larger. Solving this efficiently demonstrates basic tree navigation and optimization skills.

Algorithmic pattern used

This utilizes a Tree Traversal / Binary Search pattern. Because of the BST property, the logic is incredibly straightforward:

• If both p and q have values less than the current node's value, the LCA must lie in the left subtree.
• If both p and q have values greater than the current node's value, the LCA must lie in the right subtree.
• If they split (one is lesser, one is greater), or if one of them equals the current node, then the current node is the Lowest Common Ancestor!

Example explanation

Consider a BST with root 6. Left child 2, Right child 8. We want the LCA of p = 2 and q = 4 (where 4 is a right child of 2).

• Start at root 6.
• Check values: p (2) < 6 and q (4) < 6. Both are smaller!
• We move down to the left child, 2.
• At node 2: p (2) == 2. We have hit one of our targets! Because p equals the current node, it's impossible for them to both be strictly in the left or right subtrees.
• Node 2 is the split point, making it the LCA.

Common mistakes candidates make

The most common mistake is over-complicating the problem by using the standard generic Binary Tree LCA algorithm (which runs a full post-order DFS). While the generic algorithm works, it takes $O(N)$ time. By utilizing the BST properties, you can simply trace a single path down the tree, reducing the time complexity to $O(H)$ (where H is the height of the tree) and requiring $O(1)$ space if done iteratively.

Interview preparation tip

For the LCA of a Binary Search Tree coding problem, always write the iterative solution. A simple while (curr != null) loop checking the < and > conditions is extremely clean, uses $O(1)$ memory, and proves to the interviewer that you don't unnecessarily rely on recursive call stacks when a simple pointer traversal is perfectly adequate.