Pattern Guide
Offline LCA (Tarjan's)
"Answer all LCA queries in O(n + q) using Union-Find. Process queries offline."
Tarjan's offline LCA processes all queries in a single DFS, answering each query when exactly one of its two nodes has been visited. Uses Union-Find with path compression: when finishing a subtree, union it with the parent. LCA(u,v) = find(v) when u is completed (v is already visited). Total: O((n + q) × α(n)) ≈ O(n + q). Requires all queries upfront (offline).
Problems you can solve with this pattern
3 problems · click any to start solving
function tarjanLCA(n, edges, queries) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
// Group queries by node
const queryList = Array.from({length: n}, () => []);
for (let i = 0; i < queries.length; i++) {
const [u, v] = queries[i];
queryList[u].push([v, i]);
queryList[v].push([u, i]);
}
const parent = Array.from({length: n}, (_, i) => i);
const find = x => parent[x] === x ? x : (parent[x] = find(parent[x]));
const visited = new Array(n).fill(false);
const answers = new Array(queries.length);
const ancestor = Array.from({length: n}, (_, i) => i);
function dfs(u, p) {
ancestor[u] = u;
for (const v of adj[u]) {
if (v === p) continue;
dfs(v, u);
// Union v into u's component, ancestor of root = u
parent[find(v)] = u;
ancestor[find(u)] = u;
}
visited[u] = true;
for (const [v, qi] of queryList[u]) {
if (visited[v]) {
answers[qi] = ancestor[find(v)];
}
}
}
dfs(0, -1);
return answers;
}Tarjan's LCA: DFS the tree. When we finish processing a node u, union(u, parent(u)) and mark u as "visited." For each query (u, v): when we encounter u and v is already visited, LCA(u, v) = find(v) (the root of v's component, which has been promoted to be the LCA ancestor). Process queries for each node when that node is being finished.
function tarjanLCA(n, edges, queries) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
// Group queries by node
const queryList = Array.from({length: n}, () => []);
for (let i = 0; i < queries.length; i++) {
const [u, v] = queries[i];
queryList[u].push([v, i]);
queryList[v].push([u, i]);
}
const parent = Array.from({length: n}, (_, i) => i);
const find = x => parent[x] === x ? x : (parent[x] = find(parent[x]));
const visited = new Array(n).fill(false);
const answers = new Array(queries.length);
const ancestor = Array.from({length: n}, (_, i) => i);
function dfs(u, p) {
ancestor[u] = u;
for (const v of adj[u]) {
if (v === p) continue;
dfs(v, u);
// Union v into u's component, ancestor of root = u
parent[find(v)] = u;
ancestor[find(u)] = u;
}
visited[u] = true;
for (const [v, qi] of queryList[u]) {
if (visited[v]) {
answers[qi] = ancestor[find(v)];
}
}
}
dfs(0, -1);
return answers;
}- Tarjan's: O(n + q) total, requires all queries upfront, simpler code
- Binary lifting: O(n log n) build, O(log n) per query, supports online queries
Tarjan's key invariant: When node u is finished and v is already visited, find(v) = LCA(u,v). The Union-Find "promotes" each finished subtree to be represented by its parent (the LCA of any query involving both a node in the subtree and any already-visited node).
Use case: When you have many LCA queries and can process all at once — preprocessing for path sum queries, counting edges on paths, etc.