Lowest Common Ancestor
The Lowest Common Ancestor (LCA) of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both u and v. A node is considered an anc...
Defining LCA and Naive Approach
The Lowest Common Ancestor (LCA) of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both u and v. A node is considered an ancestor of itself. The LCA is unique for any pair of nodes in a tree. LCA queries arise naturally in phylogenetic trees (finding common ancestors of species), hierarchical data (finding the nearest common category), and network routing.
The naive approach: given the depth of each node (precomputed in O(N) via a DFS), bring the deeper node up to the same depth by following parent pointers, then move both nodes up simultaneously until they meet. Each parent pointer follow is O(1), and in the worst case you traverse the entire height of the tree: O(N) per query for a skewed tree.
If the tree is balanced (height O(log N)), the naive approach gives O(log N) per query, which may be acceptable. But for large trees or a very large number of queries, O(N) per query is too slow, and preprocessing-based algorithms reduce the per-query cost dramatically.
Binary Lifting: O(N log N) Preprocessing, O(log N) Query
Binary lifting precomputes a table where ancestor[v][j] equals the 2-to-the-j-th ancestor of node v. With O(N log N) preprocessing, each LCA query runs in O(log N).
Build the table: ancestor[v][0] equals parent(v) for all v (computed during DFS). For j greater than zero: ancestor[v][j] equals ancestor[ancestor[v][j-1]][j-1]. This fills in O(N log N) time and space.
LCA query for u and v: first bring both to the same depth using binary lifting (jump by the largest power of two that does not overshoot the target depth). Then simultaneously lift both by decreasing powers of two until they are as close as possible without meeting. The LCA is the parent of both at that point.
An alternative O(N) preprocessing, O(1) query algorithm reduces LCA to Range Minimum Query on the Euler tour of the tree. The Euler tour visits each node multiple times, recording depth and node index at each visit. The LCA of u and v is the shallowest node in the Euler tour between any visit to u and any visit to v. A sparse table on the depths gives O(1) RMQ, making each LCA query O(1) after O(N log N) preprocessing.
Worked Example and Interview Applications
Worked example using binary lifting: in a tree with root 1 and edges 1-2, 1-3, 2-4, 2-5, find LCA(4, 5). Depth of 4 and 5 is 2. They are at equal depth. ancestor[4][0] equals 2 and ancestor[5][0] equals 2. The largest power-of-two jump that keeps them separated is 0: ancestor[4][0] equals 2 and ancestor[5][0] equals 2 — they are equal at this jump, so we do not take it. Therefore the LCA is ancestor[4][0] equals 2. Correct: node 2 is the deepest common ancestor of 4 and 5.
Find LCA(4, 3): depth of 4 is 2, depth of 3 is 1. Bring 4 up by one (the depth difference): ancestor[4][0] equals 2. Now both are at depth 1. Are 2 and 3 equal? No. Try jump of zero: ancestor[2][0] equals 1 and ancestor[3][0] equals 1 — equal, so do not jump. LCA equals ancestor[2][0] equals 1. Correct: node 1 is the root and common ancestor.
LCA is used in distance computations on trees: the distance between nodes u and v equals depth(u) plus depth(v) minus 2 times depth(LCA(u, v)). It also appears in difference array techniques on trees, where range updates on a path from u to v are handled by updating u and v and subtracting at LCA and its parent.
Interview tip: always precompute depths and parents with a single DFS before any LCA queries. For a single query, the naive approach suffices. For many queries (say Q queries on N nodes), propose binary lifting for O((N plus Q) log N) total cost, or Euler tour plus sparse table for O(N log N) preprocessing and O(Q) queries. Justify your choice based on the relative sizes of N and Q given in the problem.