Lowest Common Ancestor

Given a tree and two of its nodes, the lowest common ancestor (LCA) is the deepest node that has both of them as descendants (a node counts as its own ancestor). It comes up constantly in interviews because it's a clean test of recursive thinking on trees, and it shows up for real whenever data is organized hierarchically — finding where two subsidiaries of a company merge in an org chart, or where two instruments split apart in a sector-classification tree.

The simplest recursive solution: starting from the root, if the current node is either target, return it; otherwise recurse into both children. If both recursive calls find something, the current node is the LCA; if only one side finds something, pass that result up.

$$\text{LCA}(v) = \begin{cases} v & \text{if } v = a \text{ or } v = b \\ v & \text{if left and right recursion both return non-null} \\ \text{whichever side returned non-null} & \text{otherwise} \end{cases}$$

In plain English: the recursion bubbles a "found target" signal up from below, and the first node where signals from both children meet is the answer.

Worked example

In the tree A → (B, C), B → (D, E), find the LCA of D and E. Recursing down from A: the left subtree rooted at B finds both D and E inside it (one in each of B's own children), so B itself becomes the point where both signals meet, and B is returned all the way up as the LCA — correctly, since D and E sit right under B.

For a plain binary search tree specifically, there's a faster non-recursive shortcut: walk down from the root, going left if both targets are smaller than the current node and right if both are larger; the first node where that stops being true is the LCA, found in $O(h)$ steps without touching the recursive template at all.