AlgoMaster Logo

Graph Valid Tree

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A tree is an undirected graph that is connected and has no cycles. So the question reduces to: given n nodes and a list of edges, does this graph satisfy both conditions?

A property of trees simplifies this check. A graph with n nodes is a valid tree if and only if it has exactly n - 1 edges and is fully connected. The reason: n - 1 edges is the minimum needed to connect n nodes, and any connected graph with exactly n - 1 edges has no spare edge to form a cycle. Adding even one edge beyond n - 1 to a connected graph creates a cycle, and dropping below n - 1 leaves the graph disconnected. So checking edge count plus connectivity is enough.

This removes the need for separate cycle detection. If the edge count is exactly n - 1, the only way the graph can fail to be a tree is by being disconnected.

Key Constraints:

  • 0 <= edges.length <= 5000 → Edge count is given independently of n. Since a valid tree has exactly n - 1 edges, comparing edges.length against n - 1 is a constant-time first filter that rejects most invalid inputs before any traversal.
  • 1 <= n <= 2000 → n is small, so an O(n + e) traversal or near-linear Union Find runs comfortably. The lower bound n >= 1 also means n - 1 never goes negative, so the edge-count check is safe.
  • a_i != b_i, no self-loops or repeated edges → A single edge can never connect a node to itself or appear twice, so the edge-count rule is exact: once edges.length equals n - 1, the only remaining question is connectivity.

Approach 1: BFS

Intuition

Build the graph, then verify the two tree conditions directly. First check the edge count: if there are not exactly n - 1 edges, return false immediately. Then run BFS from node 0 and count how many nodes it reaches. If the traversal visits all n nodes, the graph is connected, and combined with the edge-count check that is enough to confirm a valid tree.

The edge count carries the cycle check for us. A connected graph with exactly n - 1 edges cannot contain a cycle, because a cycle would require a spare edge beyond the n - 1 needed to connect n nodes. So edge count n - 1 plus connectivity equals a tree, with no separate cycle detection.

Algorithm

  1. If the number of edges is not exactly n - 1, return false.
  2. Build an adjacency list from the edges.
  3. Run BFS starting from node 0, tracking visited nodes.
  4. After BFS completes, return true if the number of visited nodes equals n.

Visualization and Code

Loading animation...

BFS uses a queue to explore the graph level by level. The same connectivity check works with depth-first traversal, which some prefer to write recursively.

Approach 2: DFS

Intuition

DFS verifies connectivity the same way BFS does: check the edge count, build the adjacency list, then traverse from node 0 and confirm every node is reached. The difference is the traversal order. DFS follows one path as deep as it goes before backtracking, using either recursion or an explicit stack instead of a queue. The recursive version is compact, while an explicit stack avoids deep call stacks when the graph is a long chain.

Algorithm

  1. If the number of edges is not exactly n - 1, return false.
  2. Build an adjacency list from the edges.
  3. Run DFS starting from node 0, marking nodes as visited.
  4. After DFS completes, return true if the number of visited nodes equals n.

Visualization and Code

Loading animation...

Both BFS and DFS build the full adjacency list before traversing. The next approach skips the adjacency list entirely and processes edges one at a time, merging nodes into connected components as it goes.

Approach 3: Union Find

Intuition

Union Find (also called Disjoint Set Union) solves this without an adjacency list. Start with n isolated nodes, each its own component. For each edge, merge the two endpoints into the same component. If both endpoints of an edge already belong to the same component, that edge closes a cycle, so the graph is not a tree.

The n - 1 edge-count check would make explicit cycle detection unnecessary, but tracking cycles directly inside the union step is the standard form and works even without that check: it returns false the moment an edge connects two nodes that share a root.

Algorithm

  1. If the number of edges is not exactly n - 1, return false.
  2. Initialize a Union Find structure with n nodes, each in its own set.
  3. For each edge [a, b], attempt to union a and b. If find(a) == find(b) (they're already connected), a cycle exists, so return false.
  4. If we process all edges without finding a cycle, return true.

Visualization and Code

Loading animation...