The site's seventh Disjoint Set entry, built directly on top of
Kruskal's algorithm's own merge order rather than extending
Union-Find's core contract. Minimum
Bottleneck Spanning Tree already answers "what's the smallest possible maximum edge weight
across the whole graph?" once. Kruskal's Reconstruction Tree answers a sharper,
repeatable version of a similar question for any pair of nodes — "what's the smallest
possible maximum edge weight on some path connecting exactly these two?" — after a single
O(E log E) build, in the time it takes to find one lowest common ancestor. Binary Lifting's own path-max
extension already answers a close cousin of that question, but only once a weighted tree
already exists to query, by folding max() over every jump-table cell a query crosses.
This page builds the tree that turns a general weighted graph — not yet a tree at all —
into that queryable structure in the first place, straight from Kruskal's own edge-sorted union
sequence, and needs no fold at all once it's built: the answer sits waiting at one node.
Same seven waypoints and ten trail costs as Kruskal's Algorithm's own demo (and Minimum Bottleneck Spanning Tree's). Press Step or Run to walk the identical sorted edge list: an edge whose two endpoints are still in different components creates one new tree node, weighted with that edge's own cost, whose two children are the two components' current tree "tops" — the same union Kruskal's own Union-Find performs, just building a real node instead of only merging a set. An edge whose endpoints already share a component is rejected exactly as it is in Kruskal's own demo, and creates nothing. Once every waypoint is spanned (six merges for seven waypoints, thirteen tree nodes total), pick any two waypoints below and press Find bottleneck: the highlighted lowest common ancestor's own stored weight is the answer, with no path walk needed at query time.
Because Kruskal's own scan processes edges in non-decreasing weight order, every new tree node's
weight is greater than or equal to both of its children's weights (a leaf counts as weight
0, always merged into before anything heavier arrives). That makes the whole tree
heap-ordered: weight only ever increases walking from any leaf up toward the root,
never the reverse. The root itself ends up holding the graph's single global bottleneck value —
the same number Minimum
Bottleneck Spanning Tree computes as "the weight of the last edge accepted before the tree
finishes spanning."
The lowest common ancestor of any two leaves u and v is, by
construction, the exact tree node created at the moment u's and v's
components first merged into one during Kruskal's run — and Kruskal only just accepted the edge
that caused that merge because every cheaper edge had already been tried and had failed to connect
them. That is precisely the definition of the minimum bottleneck value between u and
v: the smallest threshold w such that keeping only edges of weight
≤ w already connects them. So weight(LCA(u, v)) is the answer,
directly, the same cut-property argument that makes Kruskal's algorithm itself correct (see Kruskal's own Why it works), just read back out of the
merge history instead of re-derived per query.
Worked example, verified against a brute-force minimax check rather than
asserted: on this page's seven-waypoint network, Basecamp and Ridge don't share a component until
the fifth merge (weight 5, the Ridge–Overlook edge) — bottleneck(Basecamp,
Ridge) = 5. Basecamp, Spring, Meadow, and Summit all stay in separate components until the
very last merge (weight 7, Overlook–Summit) — so bottleneck(Basecamp, Summit),
bottleneck(Spring, Meadow), and bottleneck(Ridge, Summit) are all
7, the same number as the network's own global bottleneck, because none of those pairs
connect any earlier than the graph as a whole does.
Matches the demo above one for one. build reuses the exact Union-Find
(path compression + union by rank) that Kruskal's own reference implementation
uses — dropping either optimization degrades this page's own build the same way Union-Find's own Pitfalls warns it degrades
Kruskal's — extended to also grow a tree alongside every merge:
function buildReconstructionTree(numNodes, edges) {
const sorted = edges.slice().sort((x, y) => x.w - y.w);
const dsuParent = Array.from({ length: numNodes }, (_, i) => i);
const rank = new Array(numNodes).fill(0);
function find(x) {
while (dsuParent[x] !== x) { dsuParent[x] = dsuParent[dsuParent[x]]; x = dsuParent[x]; }
return x;
}
const top = Array.from({ length: numNodes }, (_, i) => i); // dsu root -> its current tree-top node id
let nextId = numNodes;
const size = 2 * numNodes - 1;
const left = new Array(size).fill(-1);
const right = new Array(size).fill(-1);
const weight = new Array(size).fill(0);
const treeParent = new Array(size).fill(-1);
let merges = 0;
for (const e of sorted) {
const rootA = find(e.a), rootB = find(e.b);
if (rootA === rootB) continue; // same component already — no new node
const id = nextId++;
left[id] = top[rootA];
right[id] = top[rootB];
weight[id] = e.w;
treeParent[left[id]] = id;
treeParent[right[id]] = id;
// union by rank decides which root survives — "top" of whichever root survives
// must be repointed at the new node, regardless of which direction the attach goes
let survivor;
if (rank[rootA] < rank[rootB]) { dsuParent[rootA] = rootB; survivor = rootB; }
else if (rank[rootA] > rank[rootB]) { dsuParent[rootB] = rootA; survivor = rootA; }
else { dsuParent[rootB] = rootA; rank[rootA]++; survivor = rootA; }
top[survivor] = id;
if (++merges === numNodes - 1) break; // spanning complete
}
return { left, right, weight, treeParent, root: nextId - 1 };
}
// weight(LCA(u, v)) is the minimum bottleneck value between u and v
function bottleneck(tree, u, v) {
function depth(node) {
let d = 0;
while (tree.treeParent[node] !== -1) { node = tree.treeParent[node]; d++; }
return d;
}
let du = depth(u), dv = depth(v);
while (du > dv) { u = tree.treeParent[u]; du--; }
while (dv > du) { v = tree.treeParent[v]; dv--; }
while (u !== v) { u = tree.treeParent[u]; v = tree.treeParent[v]; }
return tree.weight[u];
}Forgetting to repoint the surviving root's "top" pointer silently detaches part of the
tree — caught by a broken variant, not just argued. A first-draft version of
build above that merges the DSU (updates dsuParent and, when there's a
tie, rank) but skips the following line (top[survivor] = id) leaves that
component's top pointer stale: the next merge touching it attaches to the old,
now-superseded node instead of the new one, so the just-created node id never gets a
parent unless it happens to be the very last node built. Run both versions on random connected
graphs (4–11 nodes each, 10 paired queries per graph): the correct version matches an independent
brute-force minimax check (binary search over distinct weights, testing connectivity with a fresh
Union-Find at each threshold) on all 170,332 queries checked across 20,000 graphs, zero mismatches;
the broken version fails 16,110 of 17,072 queries across 2,000 graphs — not a rare edge case, a
near-total break, because almost every graph eventually performs a second merge on some
component.
A disconnected graph produces a forest of reconstruction trees, not one. Same
caveat as Kruskal's own Pitfalls: if the input graph
has two pieces with no edge between them, merges never reaches
numNodes - 1, and each piece ends up as its own separate reconstruction tree with its
own root. bottleneck(u, v) for a pair in different pieces has no answer — the LCA walk
above would loop forever comparing two nodes that never meet — so a real implementation needs to
check both nodes' roots match before running the query at all.
Ties among edge weights change which specific node gets which id, never which answer a
query reports. Same invariant as an MST's total weight staying fixed across every valid
tie-break: whichever of several same-weight edges Kruskal happens to sort first decides the exact
shape of the reconstruction tree around that weight, but the threshold at which any two given nodes
first connect is a property of the graph, not of the sort's tie-breaking, so
bottleneck(u, v) comes out identical either way.
The naive LCA walk above is O(depth), not O(log n), and the
tree it walks is built once, not maintained live. The demo's own query uses the same
depth-equalize-then-climb walk as Cartesian Tree's naive LCA,
fine for one-off queries but linear in the worst case on a skewed tree. Getting every query down to
genuine O(log n) needs Binary
Lifting built on top of this tree — a second, separate O(n log n)
preprocessing pass, not something this page's construction gives for free. And unlike plain Union-Find, which absorbs a brand-new union in
near-constant time forever, this structure answers only for the graph it was built from — adding
one more edge afterward means rebuilding from scratch, not patching in one more node.
Time: O(E log E) to build, dominated by the same sort that
dominates Kruskal's own runtime (see Kruskal's own
Complexity) — the DSU operations and tree-node creation alongside it add only
O(E · α(V)), near-constant per edge. Each query then costs O(depth) with
the naive walk above, or genuine O(log n) with Binary Lifting layered on afterward (see
Pitfalls). Space: O(n) — the tree holds exactly
2n - 1 nodes for n original graph nodes: n leaves plus
exactly n - 1 internal merge nodes, one per accepted edge, never more and never fewer
for a connected input.
This site's guide, Choosing a Union-Find Variant, places this entry alongside Offline Lowest Common Ancestor and Small-to-Large Merging as a third application built on top of Union-Find rather than a fourth competing extension of it.