In union-find, why does find follow parent links to a root instead of reading one entry?
answer
- what a single entry can hold
- merges relink roots, not members
- each set is a tree, not a list
- who speaks for the whole group
- stop when an element points at itself
basics
~20 sA parent entry stores only the element x was attached to, not its group. Each set is a tree, so the group's identity is the root reached by following parent links until an element points at itself.
solid answer
~40 sUnion-find stores each set as a tree inside one `parent` array: `parent[x]` is whatever x was hung under, and an element with `parent[x] == x` is the root, the set's representative. Merging two sets relinks exactly one entry — the losing root now points at the winning root — and every other member keeps pointing where it always did. That makes a single entry a purely local fact, so the only way to name the whole group is to walk up until you hit an element that points at itself. Connectivity is then `find(a) == find(b)`: two duplicate customer records describe the same person exactly when both walks end at the same record. The walk costs O(h) for tree height h, which is why the structure spends effort keeping h small.
code
pseudocode · 12 lines// parent[i] == i marks i as the root of its set
initialize(n):
for i in 0..n-1:
parent[i] = i
find(x):
while parent[x] != x:
x = parent[x]
return x
connected(a, b):
return find(a) == find(b)go deeper
Be ready to say, in one breath, that each set is a tree, that a root points at itself, and that testing whether two items are together means comparing the two roots you walk to.
Explain why a merge touches only one entry and why that makes every interior entry stale as a group label, then give the O(h) cost of the walk and name what controls h.
Show the design tradeoff: this layout buys cheap merges at the price of a short climb, and the root is an internal comparison key, never an identifier you publish to downstream systems.
Own the boundary: the structure is a derived index over the evidence that caused the merges, so the durable record must be that evidence, with cluster identity assigned deliberately rather than inherited from whichever element happens to be root.
## The one question the structure answers A union-find (also called disjoint-set union, or DSU) maintains a partition of n items into groups and answers exactly two requests: **merge the groups of a and b**, and **are a and b currently in the same group?** It deliberately answers nothing else — it will not list a group's members, will not split a group, and will not tell you *why* two items are together. A concrete setting: a customer-data service is folding duplicate identity records together. Each record is one slot in the structure. Every time a new piece of evidence arrives — two records share a phone number, two records share a verified email address — the service merges those two records' groups. At any moment the service must be able to ask: do records 41 and 90210 describe the same person? ## What is actually stored The whole state is one integer array, `parent`, with one entry per record. `parent[x]` holds the index of another record: the one x was attached to at some past merge. An element whose entry points at itself (`parent[x] == x`) is a **root**. Initialization sets `parent[x] = x` for every x, which encodes n groups of one. A useful clarification: `parent[x] == x` means x is a root, **not** that x is alone. A root with a thousand descendants still points at itself. If you need the group's population, keep a separate `size` array and read it at the root. ## Why one entry cannot name the group The cheapest possible design would be to store the group label directly in each entry, making a lookup a single read. Union-find refuses that design, because it would make merging brutal: joining a 1-element group to a 500,000-element group would have to rewrite half a million entries. Over a stream of merges that is quadratic work. The tree representation flips the cost. A merge relinks **one** entry: the root of one tree is pointed at the root of the other. Nothing else moves. That is why an interior element's entry goes stale the moment its old root stops being a root — the entry was never a claim about the group, only a claim about a single hop upward. Reading it tells you who x hangs under, which is one link in a chain of unknown length. | Operation | Tree form (union-find) | Store the label in every entry | |---|---|---| | Merge two groups | relink one entry | rewrite one whole group | | Test membership | walk to the root | one read | Union-find takes the left column because merge-heavy workloads dominate: the walk can be made extremely short, while rewriting a whole group cannot be made cheap. ## find and the connectivity test `find(x)` climbs parent links until it reaches an element pointing at itself and returns that root — the set's **representative**. `connected(a, b)` is simply `find(a) == find(b)`. Note what this does *not* require: the two records need never have been merged with each other directly. They are connected if a chain of merges links them, which is exactly the dynamic-connectivity semantics the identity service wants — record A shares a phone with B, B shares an email with C, so A and C are one person. ## The representative is arbitrary and unstable Which record ends up as root is an artifact of merge order and merge policy. It changes as merges continue: today's root becomes tomorrow's interior node. So the root is a fine *internal* label for comparing two elements right now, and a bad *external* identifier. If a downstream system needs a durable customer id for the merged cluster, store that id alongside the root and carry it across on merge; do not hand out the root index itself. ## What the walk costs The walk is O(h), where h is the height of that element's tree. Nothing so far bounds h: a careless merge policy can build one long chain, and then a single lookup touches a large fraction of the records. Everything else in this structure — attaching the smaller tree under the larger, and flattening the path while you walk it — exists to keep h tiny, which is what turns O(h) into a near-constant amortized cost over a sequence of operations. So the honest first-encounter summary is: one array, roots point at themselves, merges move one link, and membership is a short climb rather than a read.
- How do you initialize the structure, and what does that starting state mean?Every element's parent entry points at itself, so there are n roots and n singleton groups, and any two distinct elements report as unconnected. If you also track sizes, every entry starts at 1. Initialization is O(n) and is the only moment the whole array is written.
- How expensive is find in this bare form, and what makes it slow?It is O(h) for the height of that element's tree. Nothing in the bare version bounds h: if merges keep attaching the current root under a fresh element, the tree degenerates into a chain and a single lookup walks a large share of the elements. Bounding h is what the merge heuristic and path flattening are for.
- Does the root carry any meaning beyond being a label?No. Which element is root depends on merge order and merge policy, and it changes as merges continue, so it is a valid comparison key only at this instant. If a downstream consumer needs a stable identifier for the merged cluster, store that identifier at the root and carry it over on every merge rather than exposing the root index.
It is a chain of command: each person knows only their direct manager, so to find out which department someone belongs to you walk upward until you reach the person who reports to themselves.
saying these in an interview costs you the question
- Says the parent entry directly names the set an element belongs to
- Thinks a merge rewrites the parent entry of every member
- Treats the root index as a stable, externally meaningful group id
- Claims find is constant time because it is just one lookup
- Reads an element pointing at itself as meaning it is alone