DSA Tracker

Visualize

Graph Valid Tree

Union-find: n-1 edges is necessary, a cycle check is what makes it sufficient

time O(n * α(n))space O(n)

A tree on n nodes always has exactly n - 1 edges, so that count is the first, cheap filter — but it is not proof by itself: a graph can hit that exact count by combining one small cycle with a disconnected leftover piece, which is exactly the graph below. The real check is union-find: start every node in its own set, and for each edge ask whether its two endpoints are already in the same set. If they are, the edge would close a loop, so the graph is disqualified on the spot; otherwise merge the two sets and continue. Reaching the last edge without ever finding a shared set is what actually proves both 'no cycles' and 'fully connected' at once.

Details

Animated on: n = 5, edges = [[0,1],[1,2],[2,0],[3,4]] — exactly n-1 = 4 edges, but is this a valid tree?

Problem:Graph Valid TreeMedium

Union-find: n-1 edges is necessary, a cycle check is what makes it sufficient

step 1 / 9

Undirected graph as given

5 nodes and 4 edges. A valid tree needs every node reachable and zero cycles — checking edge count first is cheap, but it only rules OUT some invalid graphs, so a cycle check still has to follow.

Pseudocode
1FUNCTION validTree(n, edges):
2  IF LENGTH(edges) != n - 1
3    RETURN false
4  FOR i FROM 0 TO n - 1
5    parent[i] <- i
6  FOR EACH (a, b) IN edges
7    ra <- FIND(parent, a)
8    rb <- FIND(parent, b)
9    IF ra = rb
10      RETURN false
11    parent[ra] <- rb
12  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. 5 nodes and 4 edges. A valid tree needs every node reachable and zero cycles — checking edge count first is cheap, but it only rules OUT some invalid graphs, so a cycle check still has to follow.
  2. 4 edges matches n - 1 = 4 exactly. That's necessary for a tree, but not sufficient — this same count also fits "one small loop plus a leftover component", so the shape still needs checking.
  3. Start every node as its own set — the badge on each node is its own root. Walking the edges, two nodes sharing a root when we try to connect them means a cycle.
  4. Edge (0, 1): root of 0 is 0, root of 1 is 1.
  5. Different roots (0 vs 1) — no cycle yet. Union them: 0's set now hangs off root 1. 1 edge accepted so far.
  6. Edge (1, 2): root of 1 is 1, root of 2 is 2.
  7. Different roots (1 vs 2) — no cycle yet. Union them: 1's set now hangs off root 2. 2 edges accepted so far.
  8. Edge (2, 0): root of 2 is 2, root of 0 is 2.
  9. 2 and 0 already share root 2 through the edges already accepted — adding (2, 0) would close a loop among 0, 1, 2. RETURN false immediately; edge (3, 4) is never even reached.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Graph Valid Tree in the editorAll Graph problemsBack to roadmap