Senior LevelData Structures & Algorithms
How does Binary Lifting solve Lowest Common Ancestor (LCA) queries in O(log N)?
ā Interview Prompt: Explain Lowest Common Ancestor, Binary Lifting sparse table preprocessing O(N log N), and O(log N) LCA queries.
Lowest Common Ancestor (LCA) of two nodes $u$ and $v$ in a rooted tree is the deepest node that is an ancestor of both.
Binary Lifting: $O(N \log N)$ preprocessing, $O(\log N)$ per query
ā¢
Precompute
up[v][j] = $2^j$-th ancestor of node $v$ (using sparse table).ā¢
For LCA query $(u, v)$:
1
Bring both to the same depth (lift the deeper node up).
2
Binary lift both simultaneously until they are equal ā that's the LCA.
Applications: Path queries on trees, distance between nodes, tree DP optimisations.
Code Implementation Example
typescript
const LOG = 18;
function buildBinaryLifting(
root: number, adj: number[][], n: number,
up: number[][], depth: number[]
): void {
for (let i = 0; i <= n; i++) up[i][0] = -1; // -1 = no ancestor
function dfs(u: number, p: number): void {
up[u][0] = p;
for (let j = 1; j < LOG; j++) {
if (up[u][j - 1] !== -1) up[u][j] = up[up[u][j - 1]][j - 1];
else up[u][j] = -1;
}
for (const v of adj[u]) if (v !== p) { depth[v] = depth[u] + 1; dfs(v, u); }
}
dfs(root, -1);
}
function lca(u: number, v: number, up: number[][], depth: number[]): number {
if (depth[u] < depth[v]) [u, v] = [v, u];
let diff = depth[u] - depth[v];
for (let j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[u][j];
if (u === v) return u;
for (let j = LOG - 1; j >= 0; j--)
if (up[u][j] !== up[v][j]) { u = up[u][j]; v = up[v][j]; }
return up[u][0];
}š”Binary Lifting LCA with O(N log N) preprocessing and O(log N) queries.
šÆ Interview Key Takeaway
Binary Lifting computes 2^j-th ancestors in O(N log N). LCA queries use binary search over ancestral levels. Foundation for tree path queries and HLD.
#DSA#LCA#Binary Lifting#Tree#Senior
Back to all Data Structures & Algorithms Questionsā