Lowest Common Ancestor (LCA)
The LCA of two nodes p and q in a tree is the deepest node that has both p and q as descendants (a node can be a descendant of itself).
LCA = 'where do two cousins meet at the family reunion?' Trace both family lines upward until they share the same ancestor. The deepest shared grandparent is the LCA.
Naive: for each node, DFS to check if p and q are in its subtrees — O(n) per query. Recursive: if root is null or root is p or q, return root. Otherwise recurse left and right — if both return non-null, root is LCA; otherwise return the non-null one. For BST: if both < root go left, if both > root go right, else root is LCA — O(h) time. For sparse LCA queries (competitive programming), binary lifting achieves O(log n) per query after O(n log n) preprocessing.
Binary lifting: precompute ancestor[node][k] = 2^k-th ancestor of node for k up to log(n). To find LCA(u, v): bring both to same depth by jumping the shallower one up, then binary-lift both simultaneously until they meet. This is O(log n) per query. For LCA on general graphs (not trees), reduce to RMQ (range minimum query) problem: DFS Euler tour gives a sequence where LCA corresponds to minimum depth node between first occurrences of u and v. Farach-Colton and Bender algorithm achieves O(n) preprocessing, O(1) query.
For a BST, LCA is O(h) — just navigate left or right based on values. For a generic binary tree, the recursive O(n) approach is elegant: return p or q when found, propagate non-null up, return current node when both children are non-null. I mention that binary lifting is the production approach for multiple LCA queries — O(n log n) preprocessing, O(log n) per query. In interviews I'd implement the recursive approach and mention the optimization exists.
The recursive LCA returns the LCA even if only one of p or q exists in the tree — it returns whichever node it found. If the problem guarantees both nodes exist, this is correct. If not, you need to verify both were actually found, which requires additional logic.