LeetCode 261 · Medium · Graphs

Graph Valid Tree

Given n nodes labelled 0 to n − 1 and a list of undirected edges, decide whether the edges form a tree: every node connected, and no cycle.

O(V + E)time
O(V + E)space
DFS with prevno cycle + all visited

n 1–10 · up to 12 distinct pairs [u, v], nodes 0 to n − 1, no self-loops

Call stack dfs(i, prev) frames, bottom → top

visit in the order nodes were added

private List<List<Integer>> adj;private Set<Integer> visit;public boolean validTree(int n, int[][] edges) { if (n == 0) { return true; } adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } visit = new HashSet<>(); return dfs(0, -1) && n == visit.size();}private boolean dfs(int i, int prev) { if (visit.contains(i)) { return false; // reached twice: a cycle } visit.add(i); for (int j : adj.get(i)) { if (j == prev) { continue; // the edge we came in on } if (!dfs(j, i)) { return false; } } return true;}
i
—
prev
—
adj.get(i)
—
visit.size()
0
n
—

Why it works

  1. Brute force would try removing edges or check every pair of nodes for two different paths: far worse than O(V + E). A tree is simply connected and acyclic, and one DFS checks both.
  2. Invariant: an undirected DFS that meets an already visited node, other than the one it just came from, has found a second path to it: a cycle. Passing prev is what lets the edge back to the parent be ignored, since every undirected edge appears in both adjacency lists.
  3. Connected check: a DFS from node 0 with no cycle visits exactly the piece containing 0. The graph is one piece only when visit.size() == n. Both checks cost O(V + E) together.
  4. Pitfall: forgetting prev makes every edge look like a cycle (0 → 1 → back to 0). And "no cycle" alone is not enough: the two-pieces preset has no cycle but is not a tree.
  5. Shortcut: a tree on n nodes has exactly n − 1 edges, so many solutions return false early when edges.length != n - 1; union-find (as in Redundant Connection, 684) is the other common approach.