Why does union-find union by size or rank instead of always attaching the first root to the second?
answer
- picture a million merges arriving in order
- what shape does blind attaching build
- which of the two trees should give way
- height rises only when equals meet
- and then the element count doubles
basics
~20 sAttaching blindly can build one long chain: a million sequential merges produce a path a million links deep, so every lookup walks O(n). Hanging the smaller tree under the larger caps height at O(log n).
solid answer
~50 sThe merge direction is the whole difference between a usable structure and a linked list with extra steps. If union always points the first root at the second, feeding it merges of the form (0,1), (1,2), (2,3), … over a million records builds a single chain, and from then on every connectivity test walks the whole chain — O(n) per lookup. Union by size fixes it by comparing the two trees and hanging the smaller root under the larger; union by rank does the same using a stored upper bound on height. Either way a tree's height can only increase when two trees of equal height merge, and that merge at least doubles the element count, so height stays at O(log n) over n elements. The cost is one extra integer array and one comparison per merge, and it is what makes the later path-flattening heuristic pay off.
code
pseudocode · 11 lines// size[r] is meaningful only when r is a root
union(a, b):
ra = find(a)
rb = find(b)
if ra == rb:
return false // already one set, nothing to merge
if size[ra] < size[rb]:
swap(ra, rb) // ra is now the larger root
parent[rb] = ra
size[ra] = size[ra] + size[rb]
return truego deeper
Recall the rule in one line — the smaller tree hangs under the larger — and be able to describe the chain that forms when merges always point the first root at the second.
Explain the height argument out loud: height rises only when equal-height trees merge, and that merge doubles the element count, so height stays under log2 of n.
Show what the guarantee is and is not — a logarithmic ceiling on height, not balance — and know that flattening alone leaves you roughly logarithmic and only repairs damage after the fact.
Frame it as a cost-of-defect call: an extra array and one comparison buys a bound that holds under adversarial merge order, which is what lets you promise a latency figure for a workload whose input order you do not control.
## The failure this heuristic exists to prevent Take the simplest possible merge rule: `parent[find(a)] = find(b)` — always point the first root at the second. Now feed it a stream of 10^6 merges shaped like (0,1), (1,2), (2,3), …, (n-2, n-1). This is not an adversarial construction; it is what you get when identity records arrive in insertion order and each new record shares a key with the one before it. After the first merge, 0 hangs under 1. After the second, the root of 0's tree — which is 1 — hangs under 2. After the third, 2 hangs under 3. The result is one chain of length n: element 0 points at 1, which points at 2, and so on to the single root. Every subsequent `find(0)` walks a million links. A structure sold as near-constant has degraded to a linear scan, and the whole workload becomes quadratic. The merge rule alone caused this. Both trees existed; the rule simply chose the worse of the two attachment directions every single time. ## The rule: small under large **Union by size** keeps a second array, `size`, meaningful at roots only: `size[r]` is the number of elements in the tree rooted at r, starting at 1 for everything. On a merge, compare the two roots' sizes, hang the smaller root under the larger, and add the sizes at the new root. **Union by rank** keeps `rank[r]` instead — an upper bound on the tree's height, starting at 0. Hang the lower-rank root under the higher-rank root; if the two ranks are equal, pick either and increment the winner's rank by one. The two variants are near-equivalent in practice; size has the pleasant side benefit that `size[find(x)]` reports how many records the merged identity cluster contains. ## Why the height bound holds The argument for rank is short enough to say out loud. A tree's height only rises when the two merged trees have the same height — in every other case the shorter tree disappears inside the taller one and the height is unchanged. And a tree of height h built this way contains at least 2^h elements, because reaching height h required merging two trees of height h-1, each of which already held at least 2^(h-1). Turning that around: with n elements, h is at most log2(n). For a million records that is 20 links instead of a million. The same accounting works for size: each time an element's depth increases by one, it was in the smaller of the two trees, so the size of its tree at least doubled. Depth can therefore increase at most log2(n) times over an element's whole lifetime. Note the exact promise. Union by size buys a **logarithmic height bound**, not a balanced tree, and not any guarantee about the shape of individual subtrees. It is a ceiling, not a shape. ## Flattening on the way up, and its variants The merge heuristic is only half the story. The other half is flattening: since the walk in find already visits every node on the path to the root, it can cheaply repoint those nodes closer to the root. - **Full path compression** points every node on the traversed path directly at the root. It needs either recursion or a second pass down the path you just climbed. - **Path halving** points every other node at its grandparent during the single upward pass — one loop, no recursion, no second traversal, no extra storage. Both flatten aggressively enough that, combined with union by size or rank, the amortized cost per operation collapses to the near-constant inverse-Ackermann bound. Halving is often preferred purely because it is a single tight loop; the asymptotics are the same. ## Is the merge heuristic still needed if you flatten? Yes, on two counts. Flattening alone, with the naive merge direction, gives roughly logarithmic amortized cost — good, but not the near-constant bound, and the analysis no longer has a height ceiling to lean on. And flattening only helps *after* a path has been walked once: the first traversal of a degenerate chain still pays for its full length, so a workload with few repeated lookups gets little benefit. Union by size prevents the tall tree from ever forming, which is a stronger guarantee than repairing it afterwards. ## What it costs One extra integer array, one comparison and one addition per merge, and a possible swap of two local variables. In exchange, the worst case for a single lookup drops from O(n) to O(log n) before flattening is even considered. This is one of the cheapest asymptotic wins in the whole structure catalogue, which is why the naive merge direction should be treated as a bug rather than a simplification.
- What exactly is rank, and why is it not the true height once paths are flattened?Rank starts at 0 and increments only when two equal-rank roots merge, so it is an upper bound on height rather than a measurement. Flattening shortens real paths but ranks are never decreased, so ranks drift above the true heights. That is harmless: the bound stays valid, and the merge decision only needs a consistent ordering.
- If you already flatten paths during find, is union by size still worth keeping?Yes. Flattening alone leaves roughly logarithmic amortized cost and repairs damage only after a path has been walked once, so the first traversal of a degenerate chain pays in full. Union by size prevents the tall tree from forming at all and bounds any single lookup at O(log n). Together the two heuristics give the near-constant amortized bound.
- How do you get the population of an element's group for free from this?Keep the size array current at roots — each merge adds the two counts at the surviving root — and read `size[find(x)]`. Reading the size entry of a non-root is the classic bug: interior entries are stale from whenever that element last was a root.
saying these in an interview costs you the question
- Calls the attachment direction an arbitrary style choice
- Claims path flattening alone makes merge direction irrelevant
- Says union by size guarantees a perfectly balanced tree
- Thinks the merge relinks every element of the smaller tree
- Reads the size entry of a non-root element