Difficulty: MediumGraphs

Graph Valid Tree

Problem in Plain English

Given a node count and undirected edges, decide whether they form exactly one tree. A valid tree connects every node with no cycles.

Problem Statement

You are given n nodes labeled 0 to n - 1 and an undirected edges list.

Return true when the edges form a valid tree: every node reachable from every other node, with no cycles. Any connected graph with exactly n - 1 edges qualifies.

Constraints

$1 \le n \le 2000$
$0 \le \text{edges.length} \le 5000$
Each edge has exactly two node labels.
$0 \le a,b < n$
No duplicate edges.

Examples

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Four edges link all five nodes with no cycle, which is exactly a tree.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

Edges 1-2, 2-3 and 1-3 close a cycle, so the graph cannot be a tree.

Example 3

Input: n = 1, edges = []
Output: true

The single node is connected to itself by the empty path. It needs no edges and contains no cycle.

Example 4

Input: n = 4, edges = [[0,1],[1,2],[2,0]]
Output: false

The edge count is n - 1, but nodes 0, 1 and 2 form a cycle and node 3 is isolated. Counting edges alone would accept this invalid graph.

Example 5

Input: n = 4, edges = [[0,1],[2,3]]
Output: false

Both components are individually acyclic, but there is no path from 0 to 2. Two edges are fewer than the three needed to connect all four nodes.

Intuition

A tree uses one edge to attach each new node to the nodes already connected, so it needs exactly n - 1 edges and cannot join two nodes already linked by a path. In Example 1, 0 attaches 1, 2 and 3, then 1 attaches 4. The edge count alone is insufficient: a triangle plus an isolated node has three edges on four nodes but is not connected. DFS checks reachability and cycles directly; union-find remembers connected groups without constructing adjacency lists.

Approaches

DFS Connectivity

Solution Details

Reveal DFS Connectivity: intuition, complexity, and code

Intuition

Build adjacency lists and run depth-first search from node 0. Carry the parent so the reverse direction of an undirected edge is not mistaken for a cycle. A stack of explicit traversal frames preserves the recursive DFS order while safely handling a 2000-node chain in Python. Reject the wrong edge count first, then reject a non-parent revisit or an unreachable node.

Step-by-Step Logic

Reject unless the number of edges equals n - 1; Example 1 has four edges for five nodes. Add each edge to both endpoints' adjacency lists, preserving input order.
Mark node 0 and push its frame (node, parent, next-neighbor index) = (0, -1, 0). At each iteration resume the top frame at its next neighbor; remove a frame only when all its neighbors have been checked.
Advance the frame index before descending. Skip only the parent, reject an already visited non-parent neighbor, otherwise mark the neighbor and push its fresh frame. Example 1 descends 0 to 1 to 4.
When 4 and then 1 finish, resume 0 at neighbor 2; after 2 finishes, visit 3. The explicit frame remembers which neighbor comes next without re-scanning earlier ones.
Once the stack empties, accept only if every node is marked. Example 1 marks {0,1,4,2,3}, so return true; a separate component would leave unmarked nodes.

Why It Works

Every pushed node has a path from 0 through the frames that discovered it. Marking on discovery ensures each node has at most one frame. Ignoring its parent skips exactly the reverse copy of the discovering edge; every other visited neighbor would complete a cycle through previously discovered paths. Therefore an accepted traversal has no cycle. When the stack empties, all adjacency entries reachable from 0 have been examined, so an unmarked node proves disconnection and all marked nodes prove connectivity. Trees have n - 1 edges, so the initial count rejection cannot reject a valid tree. Together the cycle and connectivity checks accept exactly trees.

Dry Run

DFS Connectivity: variable states at each step
Action	Frame stack after action (node,parent,next index)	Visited	Decision
Count four edges; enter 0	[(0,-1,0)]	{0}	count passes
0 examines 1; enter 1	[(0,-1,1),(1,0,0)]	{0,1}	fresh node
1 examines 0	[(0,-1,1),(1,0,1)]	{0,1}	skip parent
1 examines 4; enter 4	[(0,-1,1),(1,0,2),(4,1,0)]	{0,1,4}	fresh node
4 examines 1	[(0,-1,1),(1,0,2),(4,1,1)]	{0,1,4}	skip parent
4 exhausted; pop	[(0,-1,1),(1,0,2)]	{0,1,4}	resume 1
1 exhausted; pop	[(0,-1,1)]	{0,1,4}	resume 0
0 examines 2; enter 2	[(0,-1,2),(2,0,0)]	{0,1,4,2}	fresh node
2 examines 0	[(0,-1,2),(2,0,1)]	{0,1,4,2}	skip parent
2 exhausted; pop	[(0,-1,2)]	{0,1,4,2}	resume 0
0 examines 3; enter 3	[(0,-1,3),(3,0,0)]	{0,1,4,2,3}	fresh node
3 examines 0	[(0,-1,3),(3,0,1)]	{0,1,4,2,3}	skip parent
3 exhausted; pop	[(0,-1,3)]	{0,1,4,2,3}	resume 0
0 exhausted; pop	[]	{0,1,4,2,3}	all five marked: return true

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V + E)

V = n and E = edges.length. Rejected edge counts cost O(1) time and space. Otherwise adjacency allocation holds V lists and 2E entries, the visited array holds V flags, and at most V constant-size frames exist. Each adjacency entry is examined once and the final visited scan costs O(V). Neither the input edges nor their rows are mutated. The explicit stack avoids language recursion limits.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3import java.util.ArrayDeque;4
5class Solution {6    public boolean validTree(int n, int[][] edges) {7        if (edges.length != n - 1) return false;8        List<List<Integer>> graph = new ArrayList<>();9        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());10        for (int[] edge : edges) {11            graph.get(edge[0]).add(edge[1]);12            graph.get(edge[1]).add(edge[0]);13        }14        boolean[] visited = new boolean[n];15        ArrayDeque<int[]> stack = new ArrayDeque<>();16        visited[0] = true;17        // Each frame stores node, parent, and next adjacency index to resume.18        stack.push(new int[] {0, -1, 0});19        while (!stack.isEmpty()) {20            int[] frame = stack.peek();21            int node = frame[0];22            if (frame[2] == graph.get(node).size()) {23                stack.pop();24                continue;25            }26            // Advance before descent so backtracking never repeats this edge.27            int next = graph.get(node).get(frame[2]++);28            if (next == frame[1]) continue; // Reverse copy of the tree edge.29            if (visited[next]) return false;30            visited[next] = true;31            stack.push(new int[] {next, node, 0});32        }33        for (boolean seen : visited) if (!seen) return false;34        return true;35    }36}

Hints

Hint 1

Count first: a tree on n nodes always has exactly n - 1 edges, so any other count answers false at once.

Hint 2

For the rest, test both halves: no cycles plus every node reachable means a tree.

Hint 3

With union-find, an edge joining two nodes of the same group is the cycle, and n - 1 successful merges prove connection.

Edge Cases

One node with no edges returns true; no special rejection of an empty edge list is needed.
A triangle on nodes 0, 1 and 2 with node 3 isolated has n - 1 edges but returns false. A disconnected forest such as [[0,1],[2,3]] also fails, this time already at the count check.
A 2000-node path is a valid tree; explicit DFS frames avoid Python's default recursion depth limit. A star of the same size tests a wide adjacency list.
If a self-loop is supplied, it cannot belong to a tree: it either fails the count or hits the non-parent revisit / equal-root test. Duplicate edges are excluded by the input contract; the DFS parent shortcut relies on that contract.

Common Mistakes and Interview Tips

Accepting n - 1 edges without a structural test; Example 4 has that count but contains a triangle and an isolated node.
Treating the reverse undirected edge as a cycle; skip the parent, while still rejecting other visited neighbors.
Using recursive Python DFS on a legal 2000-node chain without accounting for the interpreter's recursion limit. The explicit-frame version preserves DFS without changing interpreter settings.
Unioning raw parent values rather than roots, or incrementing rank on every merge. Rank changes only when equal-rank roots are linked.
Interview tip: prove that each successful union reduces the number of components by exactly one. That explains why a separate final connectivity check is unnecessary after n - 1 successful unions.

Key Takeaway

Tree validation splits into counting edges and testing structure; union-find folds both into one pass by treating a redundant union as a cycle.