1. One-Liner
The LCA of nodes u and v in a rooted tree is the deepest node that is an ancestor of both.
2. The Problem It Solves
Many tree queries reduce to LCA: distance(u,v) = depth(u)+depth(v)−2·depth(LCA), path min edge, network routing “meeting point”. On a static tree, preprocess once, answer many pairs fast.
3. The Core Idea
Binary lifting: store 2^k-th ancestor of each node. Lift the deeper node to equal depth, then lift both together from the highest k down until parents match. Euler tour + RMQ is another O(1) query approach with larger build.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | DFS from root: depth and immediate parent up[0][v]. |
| 2 | Fill up[k][v] = up[k-1][ up[k-1][v] ]. |
| 3 | Align depths using binary representation of depth difference. |
| 4 | If u==v, done. |
| 5 | For k from log n down to 0: if up[k][u] ≠ up[k][v], move both up. |
| 6 | Return parent of u (or v). |
5. Dry Run Example
Line tree 1—2—3—4. LCA(2,4)=2: raise 4 to depth of 2, then climb together.
6. Key Properties
| Fact | Detail |
|---|---|
| Preprocess | O(n log n) time/space |
| Query | O(log n) per pair |
| RMQ variant | O(n log n) build, O(1) query |
7. Where It Is Used
| Domain | Use |
|---|---|
| Network routing | Convergence points |
| Bioinformatics | Phylogenetic trees |
| Competitive programming | Distance on tree |
8. Interview Tips
Connect to binary representation of jumps. Edge case: one node ancestor of other. Alternative: Tarjan offline algorithm.
9. Comparison with Other Algorithms
| Method | Preprocess | Query |
|---|---|---|
| Binary lifting | O(n log n) | O(log n) |
| Euler + RMQ | O(n log n) | O(1) |
| Tarjan | O(n + q α) | Offline batches |
10. Complexity
| -- | -- |
|---|---|
| Space | O(n log n) for up table |
| Query | O(log n) |
Implementation Example (PYTHON)
from math import floor, log2
def lca(adj, root, u, v, n):
L = floor(log2(n)) + 1
up = [[-1] * n for _ in range(L)]
dep = [0] * n
def dfs(x, p):
up[0][x] = p
for y in adj[x]:
if y != p:
dep[y] = dep[x] + 1
dfs(y, x)
dfs(root, -1)
for k in range(1, L):
for x in range(n):
if up[k - 1][x] != -1:
up[k][x] = up[k - 1][up[k - 1][x]]
if dep[u] < dep[v]:
u, v = v, u
diff = dep[u] - dep[v]
for k in range(L):
if diff >> k & 1:
u = up[k][u]
if u == v:
return u
for k in range(L - 1, -1, -1):
if up[k][u] != up[k][v]:
u, v = up[k][u], up[k][v]
return up[0][u]