The site's eleventh node-linked trees entry, and the piece
missing from both of this category's other tree-path structures.
Offline LCA answers ancestor
queries in O(1) but only in one batch, all known up front.
Binary Lifting drops that restriction — any
query, any order, any time — by precomputing a static O(n log n) jump table. Neither
one can answer "what's the sum of every node's value between u and v,"
and neither can cheaply handle a single value changing: Binary Lifting's whole table would need
rebuilding. Heavy-Light Decomposition takes a different approach entirely — flatten
the tree into a plain array, the same domain Segment
Tree and Fenwick Tree already operate over —
so that any root-to-node or node-to-node path becomes at most O(log n) contiguous
ranges of that array. Once a path is "a handful of ranges," any of this site's range structures can
sit underneath, buying point updates neither LCA structure offers.
Compute every node's subtree size with one bottom-up pass, then call the child with the
largest subtree its heavy child (ties keep whichever was found
first) — every other child is a light child, and the edge to it a
light edge. Chase heavy children down from any node and the edges form a
heavy path, called a chain; light edges are exactly the places one
chain ends and the next begins. Now do one DFS from the root that always visits the heavy child
first, before any light child, and number nodes in the order visited. Because the DFS commits to a
whole heavy chain before ever backtracking to a light child, every chain's nodes land in
consecutive positions — and so does every subtree, for the same reason (a subtree is
whatever the DFS visits before it returns to the parent). Checked programmatically, not just
reasoned about: across every stress-test tree below, every node's subtree matched
[pos[v], pos[v] + size[v] − 1] exactly, no exceptions.
The same 11-node tree Binary Lifting's own
page uses, so the two can be compared node-for-node. Heavy edges are drawn thick; light edges thin.
The row below is the flattened position array (heavy-first DFS order) — each cell shows a node, and
a thick left border marks where a new chain starts. Pick u and v and press
Find Path Sum: each jump climbs from the deeper chain's current node up to its chain
head (highlighting that whole range at once, since it's contiguous), adds it to the running total,
then hops to that head's parent — until both sides land on the same chain, where one last range
finishes the job. The compare chain-head depth checkbox is on by default (the
correct algorithm); uncheck it to see real answers break — see Pitfalls.
Every child's subtree size is at most half its parent's, except the heavy child — that's
the whole reason the heavy child is exempt. If some light child's subtree exceeded
size[parent] / 2, the heavy child (defined as the largest) would have to be at least as
big, and two children each over half the parent's size can't both fit inside a subtree that's only
one bigger than their sum. So every light edge crossed on the way up at least doubles the subtree
size left behind — a path from any node to the root can cross at most ⌊log₂ n⌋ light
edges before running out of tree, which bounds the chain count (and so the jump count) per query
at O(log n).
Measured, not just derived: on 1,290 random trees up to 2,000 nodes, the most chain-transitions
any single query needed was 10, at n = 1,502 — under
log₂(2000) ≈ 10.97. A balanced binary tree, the shape that forces the bound closest to
tight, needs exactly ⌈log₂ n⌉ or one fewer at every size tested from
n = 15 (3 transitions) up to n = 1,023 (9 transitions, against
log₂(1023) ≈ 10.00).
Matches the demo above. heavy[u] = -1 marks a leaf (no heavy child).
function buildHLD(children, root, n) {
const parent = new Array(n + 1).fill(0), depth = new Array(n + 1).fill(0);
const size = new Array(n + 1).fill(1);
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); }
}
for (let i = order.length - 1; i >= 0; i--) { // children before parents
if (parent[order[i]]) size[parent[order[i]]] += size[order[i]];
}
const heavy = {};
for (const u of order) {
let best = -1, bestSize = 0;
for (const v of (children[u] || [])) if (size[v] > bestSize) { bestSize = size[v]; best = v; }
heavy[u] = best;
}
const head = {}, pos = {};
let cursor = 0;
(function decompose(u, h) {
head[u] = h; pos[u] = cursor++;
if (heavy[u] !== -1) decompose(heavy[u], h); // heavy child first — keeps chains contiguous
for (const v of (children[u] || [])) if (v !== heavy[u]) decompose(v, v);
})(root, root);
return { parent, depth, size, heavy, head, pos };
}
function pathSum(hld, values, u, v) {
const { parent, depth, head } = hld;
let sum = 0;
while (head[u] !== head[v]) {
if (depth[head[u]] < depth[head[v]]) [u, v] = [v, u]; // deeper CHAIN, not deeper node — see Pitfalls
for (let x = u; ; x = parent[x]) { // climb u's whole chain segment at once
sum += values[x];
if (x === head[u]) break;
}
u = parent[head[u]];
}
for (let x = depth[u] > depth[v] ? u : v, stop = depth[u] > depth[v] ? v : u; ; x = parent[x]) {
sum += values[x];
if (x === stop) break;
}
return sum;
}
const t = buildHLD({ 1: [2, 3, 4], 2: [5, 6], 3: [7], 5: [8], 6: [9, 10], 10: [11] }, 1, 11);
const values = { 1: 5, 2: 3, 3: 8, 4: 2, 5: 6, 6: 1, 7: 9, 8: 4, 9: 7, 10: 2, 11: 5 };
pathSum(t, values, 8, 11); // 21 — two chain jumps: [8,5] then [11,10,6,2]The (8, 11) example is the same pair
Binary Lifting's own "beyond LCA" section
queries for the heaviest edge on that path — same route, 8–5–2–6–10–11, a different
question about it. Here: chain D (5, 8, positions 6–7) sums to 4 + 6 = 10;
one jump lands on chain A (1, 2, 6, 10, 11, positions 0–4), and the range
2..11 within it — nodes 2, 6, 10, 11 — sums to
3 + 1 + 2 + 5 = 11. Total 21, verified against a brute-force
ancestor-chain walk across 47,200 random-tree trials (n up to 60),
zero mismatches, plus the exact same check re-run against the real shipped demo script above via a
fake-DOM harness.
Comparing the two nodes' own depth instead of their chain heads' depth looks like a
harmless simplification — the loop still terminates — but it can send the walk climbing the
wrong chain, one that's already exhausted, straight past the root. Traced with real
numbers on this page's own tree: querying (8, 11), depth[8] = 3 and
depth[11] = 4, so the buggy comparison swaps to treat 11 as "the side that
still needs climbing." But 11 already sits on the root's own chain — climbing
it doesn't make progress toward merging with the other side, it consumes the one chain that has
nowhere further to go. The walk sums 11, 10, 6, 2, 1, then steps to
parent[head[1]] = parent[1] = 0, the "no parent" sentinel — and the next iteration reads
values[0], which is undefined, corrupting the running sum to
NaN for good (JavaScript's NaN poisons every arithmetic op it touches
afterward, silently).
Swept every ordered pair on this page's own 11-node tree (110 total): 46 break
outright this way, 64 happen to land on the right answer anyway (node depth and
chain-head depth agree on which side to advance often enough, by coincidence, that a few
hand-picked test queries can easily miss the bug entirely), and — on this specific tree —
0 land on a wrong-but-plausible finite number. That last part isn't universal: a
broader sweep across smaller random trees (n = 3–40) found
168 wrong-but-finite results out of 10,598 buggy trials, so a different tree shape
can absolutely produce a silently-wrong number instead of a loud NaN — this page's own
tree just happens to always crash loud when it's wrong.
Time: O(n) to build — two linear passes (sizes, then the DFS
numbering), no log n factor at all, unlike Binary Lifting's O(n log n)
table. Per query: O(log n) chain jumps, each one range read — the reference
implementation above scans that range directly, so a single jump can cost up to
O(n) in the worst case (one giant chain). Back it with
Segment Tree or
Fenwick Tree instead of a raw scan and each jump
drops to O(log n), for a real O(log² n) per path query — the
log n chains times the log n cost of querying each one. Space:
O(n).
The three structures trade the same three things off differently. Offline LCA:
O(n) build, O(α(n)) query, but every query must be known before the one
pass starts. Binary Lifting: O(n log n) build, O(log n) query, any order,
any time — but the table is static; changing one node's value means rebuilding the whole thing.
Heavy-Light Decomposition: O(n) build, O(log n) chain jumps (times
whatever the backing range structure costs per jump), online like Binary Lifting — and unlike either
LCA structure, a single node's value can be updated in O(log n) (point-update the
segment tree at its position) without touching the decomposition at all, and a whole subtree can be
queried directly, since it's already one contiguous range, something neither LCA structure answers
at any cost — they only ever reason about ancestors and paths, never "everyone below me."
This site's guide, Choosing a Search Tree, groups this entry with Binary Lifting, 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 flattens a tree into array ranges so a separate range structure can answer path queries, rather than answering ancestor queries directly the way Binary Lifting does.