Given a binary search tree 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).
Before you code
In a general binary tree this needs a full traversal. In a BST, the keys tell you which way p and q lie at every node, so one downward walk suffices.
Hints
- If both p and q are smaller than the current node, the answer is in the left subtree; if both are larger, in the right.
- Otherwise they split here (or one of them is this node): this node is the answer.
- The walk is O(h) time and O(1) space if written as a loop.
Production & complexity notes
When solving Lowest common ancestor of a binary search tree on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Binary search trees to reinforce the underlying pattern.
What it practices
Using the search tree property to discard subtrees, from Binary search trees.