Graph Valid Tree

Check whether undirected edges form one valid tree.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Graph Valid Tree: With exactly n-1 undirected edges, reaching all n nodes proves the graph is one connected acyclic tree.

Input and goalCheck whether undirected edges form one valid tree.

Pass the edge-count gateFor node_count = 5 and edges [[0,1],[0,2],[1,3],[1,4]], len(edges) = 4 = 5 - 1, so build the undirected adjacency lists.

012

1034

20

31

41

queueempty

Recognize it

Use this proof when an undirected graph must be exactly one tree: reject any edge count other than n-1, then test whether one traversal reaches every vertex.

Keep true

seen contains every discovered vertex and stack contains discovered vertices not yet expanded. After the n-1 gate passes, full reachability is equivalent to being a tree.

Reuse it

Combine a cheap global structural count with one local traversal invariant. Similar count-plus-connectivity proofs validate arborescences, spanning trees, and network skeletons.

Pattern: Edge count plus DFS.

Simple idea: A tree with n nodes must have exactly n - 1 edges. With that edge count, the graph is a tree if DFS can reach every node.

def valid_tree(node_count: int, edges: list[list[int]]) -> bool:
   if len(edges) != node_count - 1:
      return False

   graph = [[] for _ in range(node_count)]
   for first, second in edges:
      graph[first].append(second)
      graph[second].append(first)

   seen = {0}
   stack = [0]
   while stack:
      for neighbor in graph[stack.pop()]:
         if neighbor not in seen:
            seen.add(neighbor)
            stack.append(neighbor)
   return len(seen) == node_count

Cost: Close to $O(V+E)$ time and $O(V)$ space.