Graph Valid Tree LeetCode 261 Guide

LeetCode 261 Graph Valid Tree gives you n nodes labeled 0 to n-1 and a list of undirected edges. Your task is to determine whether these nodes and edges form a valid tree. A tree is a special type of graph — it is connected and acyclic. Both conditions must hold simultaneously.

The problem appears in LeetCode premium but is widely discussed and tested in interviews. It is a classic Union-Find and graph traversal problem that tests whether you know the mathematical definition of a tree and can verify it efficiently. The input can have up to 2000 nodes and 3000 edges.

This problem is important because it sits at the foundation of many harder graph problems. Understanding what makes a graph a tree — and how to check both properties efficiently — is a prerequisite for problems like Redundant Connection, Minimum Spanning Tree, and Number of Connected Components.

A valid tree with n nodes has exactly two equivalent definitions: (1) connected and acyclic, or (2) connected with exactly n-1 edges. These two formulations are logically equivalent for undirected graphs. If you have n nodes and n-1 edges and the graph is connected, there can be no cycles. If there were a cycle, you would need at least n edges to connect n nodes while maintaining one.

The key insight is that either condition alone is not sufficient. Having exactly n-1 edges does not guarantee connectivity — a disconnected forest with n nodes also has n-1 edges (it is just split across multiple trees). Being connected does not guarantee acyclicity — a graph with extra edges beyond n-1 can still be connected but will contain cycles.

Checking both conditions together is fast and clean. Verify edge count first as a constant-time pre-check: if edges.length != n-1, immediately return false without any graph traversal. Then verify connectivity using BFS, DFS, or Union-Find. This two-step approach is efficient and easy to reason about correctly.

Union-Find (also called Disjoint Set Union or DSU) is the most elegant approach for this problem. Initialize n components, each node in its own set. For each edge [u, v]: call find(u) and find(v) to get their root representatives. If find(u) == find(v), the two nodes are already in the same component — adding this edge creates a cycle, so return false. Otherwise, call union(u, v) to merge their components.

After processing all edges without finding a cycle, verify connectivity: the number of remaining components must be exactly 1. With the edge count pre-check (edges.length == n-1) already verified, a cycle-free graph with n-1 edges is guaranteed to be connected — so the component count check is redundant but good practice. Path compression and union by rank make each operation nearly O(1) amortized.

The Union-Find approach handles large inputs efficiently. With path compression, find() runs in nearly constant time. The entire algorithm is O(E * α(n)) where α is the inverse Ackermann function — effectively O(E) for all practical purposes. Space is O(n) for the parent and rank arrays.

The DFS/BFS approach builds an adjacency list and then traverses the graph from node 0. Track a visited set. For each node visited, mark it as seen and recursively visit all neighbors. If you encounter a neighbor that is already visited (and it is not the parent node you came from), a cycle exists — return false. After full traversal, check that all n nodes were visited to confirm connectivity.

The parent tracking is critical for undirected graphs. In a DFS over an undirected graph, every node can see its direct predecessor as a neighbor. Without parent tracking, the DFS would immediately report a false cycle the first time it looks back along the edge it came from. Pass the parent node as a parameter (DFS) or track it in a separate map (BFS) to avoid this false positive.

BFS works identically: use a queue, a visited set, and a parent dictionary. Start from node 0. Dequeue a node, mark visited, enqueue unvisited neighbors, track their parent. If a visited neighbor is not the current node's parent, a cycle exists. After BFS, check visited size equals n.

The edge count check deserves its own section because of how powerfully it simplifies the remaining logic. If edges.length != n-1, the input cannot possibly be a tree regardless of connectivity — return false immediately. This covers two distinct failure modes: too many edges (cycle exists somewhere) and too few edges (graph is disconnected).

After confirming edges.length == n-1, you only need to verify one additional condition. For Union-Find: just run union-find and check for cycles. If no cycle is found with exactly n-1 edges, the graph must be connected and therefore a valid tree. For DFS/BFS: just check that all n nodes are reachable from node 0. If all nodes are visited with exactly n-1 edges, there can be no cycles.

This optimization reduces the Union-Find implementation to about 15 lines and the DFS implementation to about 20 lines. The clean separation — edge count as the fast reject, traversal as the deep check — makes the code easy to read, test, and explain in interviews.

Python Union-Find (15 lines): define parent list with parent[i]=i, define find with path compression as one-liner (parent[x] = find(parent[x]) or recurse), define union. In validTree: check len(edges)!=n-1 return False; for u,v in edges: pu,pv=find(u),find(v); if pu==pv: return False; parent[pu]=pv; return True. This is compact, readable, and runs in O(E*α(n)).

Python DFS (20 lines): build adjacency list as defaultdict(list). Check len(edges)!=n-1 return False. visited=set(). DFS function(node, parent): add to visited; for each neighbor: if neighbor==parent skip; if neighbor in visited return False; if not dfs(neighbor,node) return False; return True. Call dfs(0,-1) and return len(visited)==n. The parent parameter prevents false cycle detection on undirected back-edges.

Java follows the same logic: Union-Find uses int[] parent initialized in a loop, find() with path compression, union() merging by appending one root to the other. For DFS, use List<List<Integer>> adjacency, Set<Integer> visited, recursive helper with parentNode int param. Both solutions are O(V+E) time and O(V+E) space — linear in input size.

Graph Valid Tree is the foundational problem in the graph connectivity family. Redundant Connection (LeetCode 684) is a direct extension: given a tree plus one extra edge that creates a cycle, find and remove that edge. The solution is almost identical Union-Find — the first edge that triggers find(u)==find(v) is the redundant one. Number of Connected Components in an Undirected Graph (LeetCode 323) asks for the component count rather than tree validation, using the same Union-Find structure.

Minimum Spanning Tree problems (Prim's, Kruskal's) build directly on Graph Valid Tree logic. Kruskal's algorithm for MST uses Union-Find in exactly the same way: add edges in weight order, skip any edge whose endpoints are already connected (same component). The difference is that instead of returning false on a cycle, you just skip that edge and continue. Understanding Graph Valid Tree makes MST algorithms trivially understandable.

The broader graph connectivity family includes problems like Number of Provinces (LeetCode 547), Pacific Atlantic Water Flow (LeetCode 417), and making a large connected graph. The core skills — building adjacency structures, traversing with DFS/BFS, tracking visited state, and using Union-Find for component tracking — are shared across all these problems. Mastering Graph Valid Tree gives you the mental model for the entire connectivity problem family.