Lowest Common Ancestor in Coding Interviews: From Binary Search Trees to Binary Lifting

"Find the lowest common ancestor (LCA) of two nodes" is a classic tree question that appears at almost every level of technical interview. The LCA of nodes p and q is the deepest node that has both of them as descendants (a node counts as a descendant of itself). The best approach depends on the kind of tree and how many queries you need to answer, and interviewers often walk you through several versions in one session. VERSION 1: BINARY SEARCH TREE In a BST, values tell you where to go. Starting at the root: - if both p and q are smaller than the current node, go left; - if both are larger, go right; - otherwise, the current node is where they split, so it's the LCA. def lca_bst(root, p, q): node = root while node: if p.val < node.val and q.val < node.val: node = node.left elif p.val > node.val and q.val > node.val: node = node.right else: return node Time O(h), space O(1). Mention that h is O(log n) for a balanced tree but O(n) for a skewed one. VERSION 2: GENERAL BINARY TREE (RECURSIVE) Without ordering, search both subtrees: def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: return root return left or right If p is found in one subtree and q in the other, the current node is the answer. If both are in the same subtree, that subtree's result bubbles up. Time O(n), space O(h) for recursion. Follow-up to expect: "What if p or q might not be in the tree?" The version above would return the one that exists. Fix it by counting how many targets were actually found during the traversal and returning None unless both were seen. VERSION 3: NODES WITH PARENT POINTERS If each node knows its parent, the problem becomes "find where two linked lists intersect." Walk up from p and record ancestors in a set, then walk up from q until you hit one. For O(1) extra space, use the two-pointer trick: move both pointers upward, and when one reaches the root, restart it at the other starting node. They meet at the LCA after at most two passes. VERSION 4: MANY QUERIES (BINARY LIFTING) When you have a large tree and thousands of LCA queries, preprocess once: - Compute each node's depth with BFS or DFS. - Build up[k][v], the 2^k-th ancestor of v, where up[k][v] = up[k-1][ up[k-1][v] ]. To answer a query, lift the deeper node until both are at the same depth, using the binary representation of the depth difference. If they're now equal, that's the LCA. Otherwise, for k from high to low, jump both nodes up whenever up[k][u] != up[k][v]. Their parent is the LCA. Preprocessing is O(n log n), and each query is O(log n). Alternatives worth naming include the Euler tour plus a range-minimum structure, and Tarjan's offline algorithm. COMMON APPLICATIONS - Distance between two nodes: depth[u] + depth[v] - 2 * depth[lca]. - Path queries in trees, such as checking whether a node lies on the path between two others. - Organization charts, file systems and taxonomies, if the interviewer frames it as a real-world problem. HOW TO PRESENT IT Ask early whether the tree is a BST, whether nodes have parent pointers, whether both nodes are guaranteed to exist, and how many queries there are. Those questions show you know the variants, and the answers point to the right solution. Trace your recursion on a small tree before coding. Keeping this kind of structured reasoning going under pressure is the hard part. Some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to stay on track. Learn these four versions, and LCA becomes a dependable question in any tree round.