I built a union-find visualizer: watch union by size and path compression flatten a tree in real time

Union-Find is one of those data structures that's tiny to code, wild in its analysis (the runtime involves the inverse Ackermann function), and shows up everywhere once you know it. I built an interactive one where you merge groups, watch the trees form, and run find to see path compression flatten a tree in real time.

▶ Live demo: https://dev48v.github.io/union-find/
Source: https://github.com/dev48v/union-find

The whole API is three operations

• union(a, b) — merge the groups containing a and b.
• find(a) — return the representative (root) of a's group.
• connected(a, b) — literally find(a) === find(b).

Each group is a tree; every node points to its parent, up to a root that represents the set. The naive version:

parent = [0,1,2,3,...];          // everyone their own root
find(x)   { while (parent[x] !== x) x = parent[x]; return x; }
union(a,b){ parent[find(a)] = find(b); }

That works — but sloppy unions can string nodes into a linked list, making find O(n). Two optimizations fix that, and the demo shows both.

Optimization 1: union by size

Always hang the smaller tree under the larger root:

union(a, b) {
  let ra = find(a), rb = find(b);
  if (ra === rb) return;                 // already together
  if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
  parent[rb] = ra;                        // smaller under larger
  size[ra] += size[rb];
}

This alone keeps tree height at O(log n) — a big tree never gets deeper by absorbing a small one. In the demo you can see it: merge sets and the shallow one always attaches under the deep one's root.

Optimization 2: path compression

When find walks to the root, re-point every node on the path straight at the root:

find(x) {
  let root = x;
  while (parent[root] !== root) root = parent[root];
  while (parent[x] !== root) { const nx = parent[x]; parent[x] = root; x = nx; }
  return root;
}

Run find on a deep node in the demo and watch the amber path collapse flat — every node on it now points directly to the root, so the next find is a single hop. The structure literally gets faster the more you query it.

Why the runtime is a party trick

With both optimizations, m operations on n elements run in O(m · α(n)), where α is the inverse Ackermann function. α(n) is ≤ 4 for any n that fits in the observable universe — so it's constant in every practical sense, but it is not technically O(1). It's one of the few places a real algorithm's tight bound is that exotic.

Where you'll actually use it

• Kruskal's minimum spanning tree — add the cheapest edge that doesn't form a cycle; "would this form a cycle?" is exactly connected(a, b).
• Cycle detection in an undirected graph.
• Connected components — after all unions, count the distinct roots.
• Percolation / network connectivity, image flood-fill regions, account/friend "same cluster" checks.

Merge some nodes, compress a path, and watch the disjoint-set count fall toward 1. If it made union-find click, a star helps others find it: https://github.com/dev48v/union-find