Pattern Guide
Lowest Common Ancestor (LCA)
"Find common ancestor of two nodes. Binary lifting O(n log n). Euler tour + RMQ O(n)."
Lowest Common Ancestor (LCA) of nodes u and v is the deepest node that is an ancestor of both. Three algorithms: (1) Binary lifting — precompute 2^k-th ancestors in O(n log n), query in O(log n); (2) Euler tour + sparse table RMQ — O(n log n) preprocessing, O(1) query; (3) Tarjan's offline — O(n + q) using Union-Find. LCA is fundamental for tree path queries, distance between nodes, and path decomposition.
Problems you can solve with this pattern
5 problems · click any to start solving
class LCA {
constructor(n, edges, root = 0) {
const LOG = Math.ceil(Math.log2(n + 1)) + 1;
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
this.depth = new Array(n).fill(0);
this.anc = Array.from({length: n}, () => new Array(LOG).fill(-1));
// DFS to set depth and direct parent (anc[node][0])
const stack = [[root, -1, 0]];
while (stack.length) {
const [u, p, d] = stack.pop();
this.depth[u] = d;
this.anc[u][0] = p >= 0 ? p : u; // root points to itself
for (const v of adj[u]) if (v !== p) stack.push([v, u, d + 1]);
}
// Fill binary lifting table
for (let j = 1; j < LOG; j++)
for (let i = 0; i < n; i++)
this.anc[i][j] = this.anc[this.anc[i][j-1]][j-1];
this.LOG = LOG;
}
query(u, v) {
// Bring to same depth
if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
let diff = this.depth[u] - this.depth[v];
for (let j = 0; diff; j++, diff >>= 1) if (diff & 1) u = this.anc[u][j];
if (u === v) return u;
// Lift together until just below LCA
for (let j = this.LOG - 1; j >= 0; j--)
if (this.anc[u][j] !== this.anc[v][j]) { u = this.anc[u][j]; v = this.anc[v][j]; }
return this.anc[u][0];
}
distance(u, v) {
return this.depth[u] + this.depth[v] - 2 * this.depth[this.query(u, v)];
}
}LCA enables computing the path between any two nodes: path(u, v) = path(u, LCA(u,v)) + path(v, LCA(u,v)). Distance = depth[u] + depth[v] - 2*depth[LCA(u,v)]. Binary lifting precomputes anc[node][j] = 2^j-th ancestor. To find LCA: lift the deeper node to the same depth, then lift both together until they meet just below their LCA, then step up one more.
class LCA {
constructor(n, edges, root = 0) {
const LOG = Math.ceil(Math.log2(n + 1)) + 1;
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
this.depth = new Array(n).fill(0);
this.anc = Array.from({length: n}, () => new Array(LOG).fill(-1));
// DFS to set depth and direct parent (anc[node][0])
const stack = [[root, -1, 0]];
while (stack.length) {
const [u, p, d] = stack.pop();
this.depth[u] = d;
this.anc[u][0] = p >= 0 ? p : u; // root points to itself
for (const v of adj[u]) if (v !== p) stack.push([v, u, d + 1]);
}
// Fill binary lifting table
for (let j = 1; j < LOG; j++)
for (let i = 0; i < n; i++)
this.anc[i][j] = this.anc[this.anc[i][j-1]][j-1];
this.LOG = LOG;
}
query(u, v) {
// Bring to same depth
if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
let diff = this.depth[u] - this.depth[v];
for (let j = 0; diff; j++, diff >>= 1) if (diff & 1) u = this.anc[u][j];
if (u === v) return u;
// Lift together until just below LCA
for (let j = this.LOG - 1; j >= 0; j--)
if (this.anc[u][j] !== this.anc[v][j]) { u = this.anc[u][j]; v = this.anc[v][j]; }
return this.anc[u][0];
}
distance(u, v) {
return this.depth[u] + this.depth[v] - 2 * this.depth[this.query(u, v)];
}
}- Naive: walk up from both nodes O(n) per query
- Binary lifting: O(n log n) build, O(log n) query — most practical
- Euler tour + sparse table: O(n log n) build, O(1) query — fastest for many queries
- Tarjan's offline: O(n + q) total — best when all queries known upfront
Applications:
- Distance between nodes: dist(u,v) = depth[u] + depth[v] - 2*depth[LCA]
- Path queries: decompose into u→LCA and v→LCA segments
- HLD uses LCA concept (chain tops are LCA-related)
- Kth ancestor: binary lifting directly