data structures · node-linked trees · O(n log n) build / O(log n) per query

Binary Lifting (Online Lowest Common Ancestor)

The site's ninth node-linked trees entry, and the online counterpart to Offline Lowest Common Ancestor — that page's own text names this one as "future work" for the case Tarjan's algorithm can't handle, and Second-Best Spanning Tree's Complexity section names it too, as the structure a production implementation would reach for instead of that page's own naive per-candidate tree walk. Both forward references close here. Tarjan's algorithm needs every query known before the walk starts; binary lifting drops that requirement entirely — build the structure once, then answer LCA(u, v) for any pair, in any order, interleaved with anything else, at any time afterward.

The idea is the same doubling trick Sparse Table already uses, aimed at a tree instead of an array. Sparse Table precomputes, for every index, the combined value of the 2^k array elements starting there — each row built by combining two rows below it at an offset. Binary lifting precomputes, for every node, its 2^k-th ancestor — each row built by chasing the row below it through itself: up[k][v] = up[k-1][ up[k-1][v] ], the ancestor 2^k-1 steps up from the ancestor already 2^k-1 steps up. ⌈log₂(depth+1)⌉ rows are enough to reach any node from any other in O(log n) jumps, the same way any integer can be written as a sum of powers of two.

Try it

An 11-node tree, depth up to 4, so LOG = 3 rows (k = 0, 1, 2, jumps of 1, 2, and 4 levels) are enough. The table below the diagram is already fully built — row up[0] is just each node's parent, and rows up[1]/up[2] are each built once from the row below by the doubling formula above. Pick any two nodes and press Find LCA: u (black outline) is lifted to v's depth first, then both are jumped together, highest k first, skipping any jump that would make them collide or overshoot past their real meeting point. The equalize depth before searching checkbox is on by default (the correct algorithm); uncheck it to see two real answers break — see Pitfalls.

u v

equalize depth before searching (uncheck to see the bug)

up[k][node] — row 0 is the parent pointer, each row above doubles the jump

Pick u and v, then press Find LCA.

Why it works

Equalizing depth uses the same trick as the jump table itself: write the depth difference in binary and jump once per set bit. Take the default pair, LCA(7, 11): depth[7] = 2, depth[11] = 4, so the deeper node (11) needs to rise 2 levels — binary 10, one bit set at position 1 — so a single 2¹ jump, up[1][11] = 6, lands exactly on depth 2. No per-level walk, no matter how large the depth difference: a node 1,000,000 levels down needs at most 20 jumps, one per set bit of 1,000,000's binary form, not 1,000,000 single steps.

Once both nodes sit at the same depth, either they're already equal — one was an ancestor of the other to begin with, and that node is the answer — or the real LCA is still somewhere above both, and a second binary search finds it. Walking k from high to low: whenever up[k][u] ≠ up[k][v], both ancestors are still below the true LCA (jumping there doesn't overshoot it), so jump both and keep looking at that same k again next round only if a smaller one still differs; whenever up[k][u] = up[k][v], jumping that far would land at or past the LCA — indistinguishable from actually reaching it — so that jump is skipped, exactly the same "don't take a step that might overshoot" logic Binary Search itself relies on. What's left once every k down to 0 has been tried is two nodes exactly one edge below the LCA, and up[0] of either one names it directly. Finishing the LCA(7, 11) example: u = 6, v = 7 after equalizing, not yet equal; up[2][6] = up[2][7] = 0 (skip), up[1][6] = up[1][7] = 1 (skip), up[0][6] = 2 ≠ up[0][7] = 3 (jump: u = 2, v = 3) — and up[0][2] = 1 is the answer, matching a plain ancestor-chain walk on this page's tree.

Reference implementation

Matches the demo above. 0 is the sentinel for "no ancestor" — safe because real node IDs start at 1.

function buildBinaryLifting(children, root) {
  const parent = { [root]: 0 }, depth = { [root]: 0 };
  const order = [root];
  for (let i = 0; i < order.length; i++) {
    const u = order[i];
    for (const v of (children[u] || [])) {
      parent[v] = u; depth[v] = depth[u] + 1; order.push(v);
    }
  }
  const LOG = Math.max(1, Math.ceil(Math.log2(Math.max(...order.map(n => depth[n])) + 1)));
  const up = Array.from({ length: LOG }, () => ({}));
  for (const v of order) up[0][v] = parent[v];
  for (let k = 1; k < LOG; k++) {
    for (const v of order) {
      const mid = up[k - 1][v];
      up[k][v] = up[k - 1][mid] !== undefined ? up[k - 1][mid] : 0;
    }
  }

  function lca(u, v) {
    if (depth[u] < depth[v]) [u, v] = [v, u];   // u must be the deeper node — see Pitfalls
    let diff = depth[u] - depth[v];
    for (let k = 0; k < LOG; k++) if ((diff >> k) & 1) u = up[k][u];
    if (u === v) return u;
    for (let k = LOG - 1; k >= 0; k--) {
      if (up[k][u] !== up[k][v]) { u = up[k][u]; v = up[k][v]; }
    }
    return up[0][u];
  }

  return { lca };
}

const t = buildBinaryLifting({ 1: [2, 3, 4], 2: [5, 6], 3: [7], 5: [8], 6: [9, 10], 10: [11] }, 1);
t.lca(7, 11);                                    // 1 — O(log n), answerable at any time, any order

Pitfalls

Skipping the swap that guarantees u is the deeper node looks harmless — the jump table itself never changes — but it silently breaks any query where the caller happens to pass the shallower node first, checked with real numbers on this page's own tree. Without the swap, diff = depth[u] - depth[v] can come out negative. JavaScript's >> is an arithmetic shift, so a negative diff has every bit set in its 32-bit two's-complement form — (diff >> k) & 1 reads as 1 for every k from 0 to LOG-1, so the "equalize" loop fires every jump it has regardless of the real depth gap, walking u straight past the root to the 0 sentinel instead of stopping at the right depth.

On this page's tree, calling lca(7, 11) with the swap removed — u = 7 stays put even though v = 11 is the deeper one — returns 0 instead of the correct 1; lca(8, 11) the same way returns 0 instead of 2. Both checked by running the shipped step generator itself with the checkbox off, not just reasoned about. Every pair where the caller already happens to pass the deeper node first (or passes two nodes at equal depth) shows no symptom at all — the same "bug invisible on some inputs, wrong on others" shape Offline LCA's own pitfall has, which is exactly what makes it easy to ship unnoticed: a few manual test queries can all happen to pick the deeper node first by chance.

Beyond LCA: path-max queries

Second-Best Spanning Tree's own Complexity section names the specific job this closes: given a fixed tree with weighted edges, answer "what's the heaviest edge on the path between u and v?" for many pairs, without re-walking the path from scratch each time. The fix needs no new structure — extend the same jump table with a second value per cell, the max edge weight crossed by that jump: mx[0][v] is just the weight of the edge into v, and mx[k][v] = max(mx[k-1][v], mx[k-1][up[k-1][v]]), built alongside up in the same pass. A query does the identical depth-equalize-then-binary- search walk lca already does, folding max() over every mx cell read along the way instead of discarding it.

On this page's tree, with each node's incoming edge weighted 2→4, 3→7, 4→2, 5→5, 6→1, 7→6, 8→3, 9→8, 10→2, 11→9: the path from 8 to 11 runs 8–5–2–6–10–11, crossing weights 3, 5, 4, 1, 2, 9 — heaviest is 9 (the 10–11 edge), and the extended query returns exactly that, verified against a brute-force walk of the real path on 15,000 random-tree trials with zero mismatches (the plain lca query above was checked the same way, 25,000 trials against a brute-force ancestor-chain walk, also zero mismatches). Second- Best Spanning Tree's own naive version pays a fresh O(V) walk per leftover edge to find that same maximum; this structure answers it in O(log V) after one O(V log V) build, exactly the trade its Complexity section describes.

Complexity

Time: O(n log n) to build — log n rows, each O(n) to fill by reading one cell from the row below. O(log n) per query — at most log n jumps to equalize depth, then at most log n more in the binary search, each a single array read, no tree walk. Space: O(n log n), one ancestor pointer per (node, k) pair — more than Offline LCA's O(n), the price of answering queries in any order instead of just the ones known in advance. Worth it whenever queries can't all be collected up front, or need answering one at a time as they arrive — batch every query first and Offline LCA's plain union-find pass is both simpler and lighter.

This site's guide, Choosing a Search Tree, groups this entry with Heavy-Light Decomposition, Centroid Decomposition, and Link-Cut Tree as answering questions about a tree's own shape rather than about a set of keys stored in one — none of the four ever compares two keys against each other to decide which way to branch. Among them, it answers ancestor queries (LCA(u, v)) directly on a fixed tree, the building block Heavy-Light Decomposition and Centroid Decomposition both lean on rather than reimplement.