28 · Union-Find & Minimum Spanning Trees
#261 Graph Valid Tree
the problem
In plain words
You get n nodes labelled 0 to n − 1 and a list of undirected edges edges[i] = [a, b] (no self-loops, no edge listed twice). Return true if these edges form a valid tree — every node can reach every other node, and there is no cycle — otherwise false.
in n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
out true
Node 0 connects to 1, 2, 3, and 1 connects to 4: connected, no loop.
in n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
out false
1 → 2 → 3 → 1 is a cycle (and 5 edges is one too many for 5 nodes).
- 1 ≤ n ≤ 2000
- 0 ≤ edges.length ≤ 5000
- edges[i] = [a, b] with 0 ≤ a, b < n and a ≠ b
- No repeated edges
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnion-Find (DSU)Graph DFS / BFS traversal
A tree on n nodes has exactly n − 1 edges and is connected. So: if the count is wrong, answer false at once. With exactly n − 1 edges, "no cycle" and "connected" become the same thing — one union-find pass that never sees an edge inside one set proves both.
solutions
From brute force to optimal
Before adding u–v, walk the graph built so far; if u can already reach v, this edge makes a cycle. At the end, check everyone is reachable from node 0.
- For each edge: DFS from u in the graph so far; if it reaches v → false.
- Add the edge.
- Finally DFS from 0; if some node is unreached → false; else true.
Each of the E edges can trigger a search over the whole graph built so far.
Adjacency lists, seen array and the DFS stack.
class Solution { /** Before adding each edge, walk the graph built so far: if u can already reach v, the edge makes a cycle. */ public boolean validTree(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { if (reachable(adj, e[0], e[1], new boolean[n])) return false; // a second path → cycle adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } // No cycle so far. Connected? Everyone must be reachable from node 0. boolean[] seen = new boolean[n]; reachable(adj, 0, -1, seen); for (boolean s : seen) if (!s) return false; return true; } /** Iterative DFS from u; marks everything it reaches in seen. */ private boolean reachable(List<List<Integer>> adj, int u, int target, boolean[] seen) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(u); seen[u] = true; while (!stack.isEmpty()) { int x = stack.pop(); if (x == target) return true; for (int y : adj.get(x)) { if (!seen[y]) { seen[y] = true; stack.push(y); } } } return false; }}Check edges.length == n − 1, then BFS from node 0 and count how many nodes it reaches.
- If edges.length != n − 1 → false.
- Build adjacency lists (both directions).
- BFS from 0, marking on enqueue; return reached == n.
One pass to build the lists, one BFS that touches every node and edge once.
Adjacency lists, the queue and seen.
class Solution { /** A tree on n nodes has exactly n − 1 edges and is connected. Check the count, then BFS from 0. */ public boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; // too few → disconnected, too many → a cycle List<List<Integer>> 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]); } boolean[] seen = new boolean[n]; ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.offer(0); seen[0] = true; int reached = 1; while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.get(u)) { if (!seen[v]) { seen[v] = true; // mark on enqueue reached++; queue.offer(v); } } } return reached == n; // n − 1 edges + connected ⇒ no cycle either }}Check edges.length == n − 1; then union every edge. An edge whose ends already share a root closes a cycle → false. If none does, it's a tree.
- If edges.length != n − 1 → false.
- parent[i] = i, size[i] = 1.
- For each edge: same root → false; else link by size.
- Return true.
After the count check there are exactly V − 1 edges, each a near-constant union.
parent and size arrays — no adjacency lists.
class Solution { private int[] parent, size; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; // a tree has exactly n − 1 edges parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } for (int[] e : edges) { int ra = find(e[0]), rb = find(e[1]); if (ra == rb) return false; // already connected → this edge closes a cycle if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; } parent[rb] = ra; size[ra] += size[rb]; } return true; // n − 1 edges, no cycle ⇒ connected ⇒ a tree }}Dry run
in the room
How to say it in the interview
talk track
- Define a tree out loud: connected, no cycle — equivalently, connected with exactly n − 1 edges.
- Do the O(1) count check first; it rejects half the bad inputs immediately.
- Then: "With n − 1 edges, if no edge closes a cycle, the n − 1 merges join n pieces into one — so it's connected too."
traps
- Checking only for cycles: n = 4 with edges 0–1 and 2–3 has no cycle but isn't connected.
- Checking only connectivity: a connected graph with an extra edge has a cycle.
- Treating n = 1 with no edges as false — a single node is a valid tree.
what they ask next
Follow-ups
What if the edges were directed — is it a rooted tree?
Exactly one node has in-degree 0 (the root), every other node has in-degree 1, and everything is reachable from the root.
Which edge should be removed to make it a tree (one extra edge)?
That's Redundant Connection (LC 684): the first union that fails.
before you submit
Edge cases to test
- n = 1, no edges → true.
- n = 2, no edges → false (two pieces).
- n − 1 edges that form a triangle plus an isolated node → false.
- A 1,500-node path is a valid tree; a recursive DFS goes 1,500 calls deep on it.
practise next
Similar problems
- #684Redundant ConnectionMediumin Union-Find & MST
- #323Number of Connected Components in an Undirected GraphMediumin Union-Find & MSTLeetCode Premium
- #310Minimum Height TreesMediumin Topo Sort