Graph Valid Tree: Prove Connected + Acyclic with Union-Find
Check whether a set of edges forms a valid tree using Union-Find — the n-1 edge gate, cycle detection, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A tree is the most disciplined shape a graph can take: every node reachable, not one edge wasted, no loops anywhere. Graph Valid Tree asks you to prove a pile of edges hits that exact target — no more, no less.
The trap is thinking one condition is enough. "No cycle" alone lets the graph fall into disconnected pieces. "Connected" alone lets a redundant edge sneak a loop in. A tree needs both to be true at once, and the elegant part is that a single counting fact plus one data structure nails both in linear time.
The problem
You have n nodes labeled 0 to n - 1 and a list of undirected edges, where each edges[i] = [u, v] connects nodes u and v. Return true if these edges form a valid tree — meaning the graph is fully connected and contains no cycles.
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true // all 5 nodes joined, no loops
Input: n = 4, edges = [[0,1],[1,2],[0,2]]
Output: false // 0-1-2 form a triangle (cycle), node 3 is strandedThat second case is the one to keep in mind. It has exactly n - 1 = 3 edges, yet it is not a tree — the edges pile up into a cycle among three nodes and abandon the fourth. Passing the edge count is necessary but not sufficient on its own.
The brute force baseline
The direct approach builds an adjacency list, runs a DFS or BFS from node 0, and checks two things: did the traversal reach every node (connected?), and did it ever revisit a node through a non-parent edge (cycle?).
function validTree(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visited = new Set();
function dfs(node, parent) {
if (visited.has(node)) return false; // back edge => cycle
visited.add(node);
for (const next of adj[node]) {
if (next === parent) continue; // don't walk back the edge we came in on
if (!dfs(next, node)) return false;
}
return true;
}
return dfs(0, -1) && visited.size === n;
}This is correct and runs in O(n + e) time, but it carries baggage: you build the whole adjacency list, you must remember to skip the parent edge (an undirected edge looks like an instant cycle otherwise), and the recursion can blow the stack on a long chain. There is a leaner path that never materializes the graph at all.
The key insight
Two facts collapse the whole problem.
First, a tree on n nodes has exactly n - 1 edges. Fewer edges cannot possibly connect everything; more edges must close a loop. So edges.length !== n - 1 is an instant false in O(1) — no traversal needed.
Second, once the edge count is right, a tree is equivalent to "no cycle." If you have n - 1 edges and none of them creates a cycle, the graph is forced to be connected — there is no way to spend exactly n - 1 cycle-free edges and still leave a node isolated. So after the count gate, you only have to detect cycles.
That is precisely what Union-Find (a disjoint-set structure) does best. Treat each node as its own set. For every edge, ask: are these two endpoints already in the same set? If yes, this edge joins two nodes that were already connected — a cycle. If no, merge their sets and move on. No adjacency list, no recursion, no parent-tracking.
The optimal solution
This mirrors the algorithm the visualizer runs line for line — the n - 1 gate, a parent array, find with path compression, and a union that reports a cycle.
function validTree(n, edges) {
// A tree of n nodes has exactly n-1 edges — cheap O(1) gate.
if (edges.length !== n - 1) return false;
const parent = Array.from({ length: n }, (_, i) => i);
function find(i) {
if (parent[i] === i) return i;
return parent[i] = find(parent[i]); // path compression
}
function union(i, j) {
const rootI = find(i);
const rootJ = find(j);
if (rootI === rootJ) return false; // already connected => cycle
parent[rootI] = rootJ;
return true;
}
for (const [u, v] of edges) {
if (!union(u, v)) return false;
}
return true;
}parent[i] starts pointing at i itself — every node is its own root. find walks up to the root and rewrites parent[i] to point straight at it (path compression), so future lookups are nearly O(1). union fails the moment two endpoints share a root, because that means a path between them already existed and this edge is redundant. If every edge unions cleanly, the n - 1 gate guarantees the result is one connected, acyclic component: a valid tree.
Walkthrough
Trace n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]. The gate passes because 4 === 5 - 1. Start with parent = [0,1,2,3,4], each node its own root. find compresses paths as it goes, so the array shifts a little more than the raw union writes suggest.
| Edge | root(u) | root(v) | Same set? | Action | parent after |
|---|---|---|---|---|---|
| [0,1] | 0 | 1 | no | union: parent[0] = 1 | [1,1,2,3,4] |
| [0,2] | 1 | 2 | no | union: parent[1] = 2 | [1,2,2,3,4] |
| [0,3] | 2 | 3 | no | union: parent[2] = 3 | [2,2,3,3,4] |
| [1,4] | 3 | 4 | no | union: parent[3] = 4 | [2,3,3,4,4] |
Every edge merged two distinct sets, so union never returned false. After the loop, all five nodes chain up to root 4 — one component, no cycles — and the function returns true.
Now picture the rejecting case n = 4, edges = [[0,1],[1,2],[0,2]]. The gate passes (3 === 4 - 1). Edge [0,1] and [1,2] merge nodes 0, 1, 2 into one set. Then edge [0,2] calls find(0) and find(2) — both already resolve to the same root. union returns false, and the function bails with false. That is the cycle the edge count alone could never catch.
Complexity
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n + e·α(n)) | build parent array O(n); each edge does two finds, near-constant with path compression (α is the inverse Ackermann function, ≤ 4 in practice) |
| Space | O(n) | the parent array holds one slot per node — no adjacency list |
Because e = n - 1 whenever we get past the gate, the whole thing is effectively O(n) time and O(n) space. The DFS baseline matches the time bound but spends extra space on the adjacency list and risks deep recursion; Union-Find stays flat and iterative.
Common mistakes
- Trusting the edge count alone.
edges.length === n - 1is necessary, not sufficient. The[[0,1],[1,2],[0,2]]case has the right count and still isn't a tree. You must run the cycle check. - Checking connectivity and cycles separately. Once the count gate passes, "no cycle" already implies "connected." Adding a separate BFS to count reachable nodes is redundant work.
- Forgetting the parent edge in the DFS version. An undirected edge
u-vappears in both adjacency lists, so a naive DFS seesvrevisitinguas a cycle. You must skip the edge you arrived on. - Skipping path compression. Without it,
finddegrades to O(n) on a long chain and the whole algorithm slides toward O(n²). Theparent[i] = find(parent[i])rewrite is what keeps it near-linear. - Assuming edges are unique and self-loop-free. A duplicate edge
[0,1]appearing twice, or a self-loop[2,2], is an instant cycle — Union-Find catches both naturally because the endpoints already share a root.
Where this pattern shows up next
Union-Find and connectivity reasoning power a whole family of graph problems:
- Redundant Connection — the same cycle-detection loop, but you return the specific edge that closes the loop instead of a boolean.
- Find if Path Exists in Graph — union every edge, then ask whether two nodes share a root.
- Max Area of Island — flood-fill connectivity on a grid, the DFS cousin of set-merging.
- All Paths From Source to Target — DFS traversal on a DAG, where enumerating paths matters more than merging sets.
You can also step through Graph Valid Tree interactively to watch the parent array rewire and a cycle light up the instant two roots collide.
FAQ
Why is checking for a cycle enough to prove the graph is a tree?
Only after the edge count gate passes. A tree on n nodes has exactly n - 1 edges. If you have n - 1 edges and none of them forms a cycle, there is no way to leave any node disconnected — spending every edge to merge two previously separate groups forces all n nodes into a single component. So edges.length === n - 1 plus "no cycle detected" together guarantee connected and acyclic, which is the definition of a tree.
How does Union-Find detect a cycle?
Each node starts in its own set. For every edge [u, v], you find the root of u's set and the root of v's set. If those roots are different, the edge connects two separate groups — safe, so you merge them. If the roots are already the same, the two nodes were already connected by some earlier path, and this edge creates a second route between them: a cycle. That single root comparison is the entire cycle test.
What is the time complexity of the Union-Find solution?
Effectively O(n). Building the parent array is O(n), and each of the n - 1 edges does two find operations. With path compression, find runs in near-constant amortized time — O(α(n)), where α is the inverse Ackermann function that stays at or below 4 for any input you will ever see. Space is O(n) for the parent array, with no adjacency list required.
Can I solve Graph Valid Tree with DFS or BFS instead?
Yes. Build an adjacency list, traverse from node 0 while tracking the parent of each node to avoid false cycles on undirected edges, and confirm at the end that you visited all n nodes. It runs in O(n + e) time and is perfectly valid. Union-Find is usually preferred because it avoids building the graph, uses only an integer array, and never risks stack overflow on a long chain.
Does an empty edge list ever count as a valid tree?
Only when n = 1. A single node with no edges satisfies edges.length === n - 1 (both are 0) and has no cycle, so it is a trivial valid tree. For any n > 1 with zero edges, the count gate fails immediately — you cannot connect two or more nodes with no edges — and the function returns false.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.