Given n nodes and a list of undirected edges, return true if they form a valid tree.
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → truen = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] → false (there is a cycle)
In plain English, given N nodes (labeled 0 to N-1) and a list of undirected edges, you must determine if the resulting graph is a valid tree. A valid tree must connect all nodes together and must contain absolutely no cycles.
Think of a tree as a family's power strip setup. You have N electronics and you want to plug them all together using extension cords (edges) so that everything gets power from one single wall outlet.
If you use too few cords, some electronics won't get power (not connected).
If you use too many cords, you might accidentally plug an extension cord into another extension cord in a circle, creating a dangerous short circuit (a cycle). To perfectly connect N electronics without short circuits, you need exactlyN-1 cords. If someone hands you a box of cords and asks, "Will this make a valid power setup?", your very first move should be to just count the cords. If it's not N-1, you say "No!" immediately without even looking at how they plug in.
There is a shortcut that makes it much easier. For a graph with n nodes:
Connected + exactly n − 1 edges ⟹ no cycle.
Why: a connected graph needs at least n − 1 edges to link everything. Any extra edge must join two nodes already connected, which closes a cycle. So with exactly n − 1 edges, connectivity alone rules out cycles.
The same works the other way: acyclic + exactly n − 1 edges ⟹ connected.
So check two things, and one of them is a single comparison:
len(edges) == n - 1
the graph is connected
Check the edge count first. It is O(1) and it eliminates most invalid inputs before any traversal.
class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: if len(edges) != n - 1: # (1) return False # too few or too many, instantly wrong parent = list(range(n)) # (2) def find(x: int) -> int: # (3) while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for a, b in edges: # (4) ra, rb = find(a), find(b) if ra == rb: # (5) return False # cycle parent[rb] = ra # (6) merge return True # (7)
ts
function validTree(n: number, edges: number[][]): boolean { if (edges.length !== n - 1) return false; // (1) const parent = Array.from({ length: n }, (_, i) => i); // (2) function find(x: number): number { // (3) while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } for (const [a, b] of edges) { // (4) const ra = find(a), rb = find(b); if (ra === rb) return false; // (5) parent[rb] = ra; // (6) } return true; // (7)}
With the edge count already checked, there is nothing left to verify at the end. If n − 1 edges all merged two different components, then n − 1 merges happened, and n components reduced by n − 1 leaves exactly one. Connected, automatically.
That is why the loop can return True immediately rather than counting components afterwards.
Union by size is omitted here because path halving alone is fast enough at this size. Include it if asked; it is two extra lines.
(1) A tree with n nodes has exactly n − 1 edges. Fewer edges, and some node must be cut off. More edges, and there must be a loop. So the wrong count fails at once. With the right count, the graph is a tree exactly when it has no loop, which is what the rest checks.
(2) Union-find: every node starts as its own group, as in 4.20.10.
(3) find returns a node's group root, flattening the path as it climbs.
(4) Add each edge.
(5) Both ends already in the same group means this edge closes a loop. A tree has no loops, so the answer is false.
(6) Otherwise join the two groups.
(7) n − 1 edges and no loop means the graph is one connected tree. Each edge joined two separate groups, so n groups became exactly 1.
def validTree(self, n, edges): if len(edges) != n - 1: return False adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b) adj[b].append(a) seen = set() stack = [0] while stack: node = stack.pop() if node in seen: continue seen.add(node) stack.extend(adj[node]) return len(seen) == n # reached everything → connected
With the edge count already confirmed, the traversal only has to prove connectivity — reach every node from node 0. No cycle check is needed at all.
Without the edge-count shortcut, the DFS would have to detect cycles too, and for an undirected graph that means "I reached an already-visited node that is not the one I came from". Every undirected edge looks like a two-cycle otherwise, so the parent must be excluded:
python
def dfs(node, parent): seen.add(node) for nxt in adj[node]: if nxt == parent: continue # the edge we arrived on if nxt in seen: return False # a real cycle if not dfs(nxt, node): return False return True
That parent check is the undirected cycle rule, and it is different from the three-state rule for directed graphs in 4.20.8. Knowing which applies to which is worth more than either alone.
O(n \cdot \alpha(n)), effectively O(n), with O(n) space. The edge count check makes the whole thing O(1) for most invalid inputs. To break it down: we first do an O(1) length check. If we pass, we initialize N elements in the parent array (O(N)). We loop over exactly N-1 edges. For each edge, we do inverse-Ackermann time find and union operations (effectively O(1)). Total time is strictly bounded by O(N). Space complexity is O(N) to store the parent array. No adjacency list or recursion stack is needed.
Number of Connected Components — drop the tree requirement and count instead. 4.20.11.
Redundant Connection — n edges instead of n − 1, so find the one that closes the cycle. 4.20.10.
Minimum Spanning Tree — build a tree from a weighted graph by adding the cheapest edges that do not close a cycle. Kruskal's algorithm is this loop with the edges sorted first. 4.21.
The n − 1 fact links these problems. A spanning tree of n nodes always has exactly n − 1 edges, which is why Kruskal's algorithm stops after n − 1 successful unions.
"What makes a graph a tree?" Connected and acyclic. Then give the shortcut: connected plus exactly n − 1 edges implies acyclic.
"Why does the edge count shortcut work?"n − 1 is the minimum for connectivity; any extra edge must close a cycle.
"How do you detect a cycle in an undirected graph with DFS?" Reaching a visited node that is not the parent. Contrast it with the three-state rule for directed graphs.
"What about a self-loop or a duplicate edge?" Both are cycles, and union-find catches both without special handling.
"Is a single node a tree?" Yes, and the arithmetic already agrees.
One thing to volunteer: state the two conditions and the shortcut before writing anything. Most wrong answers to this problem check connectivity and forget cycles, or the reverse — saying both up front shows you know why the shortcut is safe.
Next:4.20.13 Word Ladder — the hardest problem in this chapter, where the graph is never built at all.