Pattern visualizer

Graph Valid Tree

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. Animated on: n = 5, edges = [[0,1],[1,2],[2,0],[3,4]] — exactly n-1 = 4 edges, but is this a valid tree?.

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

time O(n * α(n))space O(n)step 1 / 9

Undirected graph as given

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap