Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About Lowest Common Ancestor (LCA): given a rooted tree and two nodes u and v, the LCA is the deepest node that is an ancestor of both
Lowest Common Ancestor (LCA): given a rooted tree and two nodes u and v, the LCA is the deepest node that is an ancestor of both.
Binary lifting precomputes every node's 2^k-th ancestor, then answers each LCA query in O(log n) — the technique of choice for dynamic trees, tree path queries, and competitive programming.
How It Works
First a DFS from the root fills parent[] and depth[].
Then the lifting table up[k][v] = the 2^k-th ancestor of v, built from up[k][v] = up[k−1][up[k−1][v]].
A query first lifts the deeper node up to the shallower node's depth by decomposing the depth difference into powers of two; if they now meet, that node is the LCA.
Otherwise both nodes climb from the highest k downward while up[k][u] ≠ up[k][v], ending one step below the LCA, whose parent is the answer.
O(log n) per query, O(n log n) preprocessing.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Preprocessing (DFS + lifting table) | O(n log n) | O(n log n) |
| LCA query | O(log n) | O(1) |
| K-th ancestor query | O(log n) | O(1) |
| Distance(u, v) | O(log n) via depth[u] + depth[v] − 2·depth[lca] | O(1) |
Best Use Cases
- Tree path queries — sum/min/max along the path u→v via LCA
- Finding the distance between two nodes in a tree
- Rooted-tree ancestor tests ("is a an ancestor of b?")
- Determining cycles and bridge structures in trees
- Dynamic tree problems where queries must be answered fast
Worked Example
Find LCA(4, 5) in a 7-node rooted tree
Input: root 0; 0 → (1, 2); 1 → (3, 4); 2 → (5, 6); query LCA(4, 5)- 1 DFS from the root fills depth[]: node 4 is at depth 2 (under 1), node 5 is at depth 2 (under 2).
- 2 Build the lifting table up[k][v] = the 2^k-th ancestor of v.
- 3 Both nodes are at equal depth, so no lifting is needed to level them.
- 4 Walk from the highest k downward while up[k][4] ≠ up[k][5]: at k=0, up[0][4] = 1 and up[0][5] = 2 differ, so step both up.
- 5 After the loop, both nodes sit one level below the LCA; the answer is up[0][u] = 0.
- 6 Each query costs O(log n); the preprocessing is O(n log n).
Pseudocode
DFS(root) → parent[], depth[]
up[0][v] = parent[v]
for k in 1..LOG:
up[k][v] = up[k-1][up[k-1][v]] function lca(u, v):
if depth[u] < depth[v]: swap(u, v)
diff = depth[u] - depth[v]
for k in LOG..0:
if diff & (1 << k): u = up[k][u]
if u == v: return u
for k in LOG..0:
if up[k][u] != up[k][v]:
u = up[k][u]; v = up[k][v]
return up[0][u] Build Lifting Table
Binary lifting precomputes 2^k-th ancestors so LCA queries run in O(log n).