# Graph Valid Tree

> How to solve Graph Valid Tree: verify a graph is connected and has exactly n minus one edges, the signature of a tree.

- Difficulty: Medium
- Category: Graphs
- Topics: DFS, BFS, Graph, Union Find
- Published 2026-08-21

## Problem

You are given a number of nodes labeled from `0` up to `n - 1` and a list of undirected edges connecting pairs of them. Determine whether these edges form a valid tree, meaning the graph is fully connected and contains no cycle.

**Example.** With `5` nodes and edges connecting `0-1`, `0-2`, `0-3`, and `1-4`, every node is reachable and no cycle exists, so the answer is true. Adding an extra edge `2-3` creates a cycle through `0`, `2`, and `3`, so the answer becomes false.

## Key idea

A tree on `n` nodes has a precise numeric signature: it always has exactly `n - 1` edges, since that is the fewest edges that can connect `n` nodes, and any additional edge necessarily creates a cycle. So the first, cheap check is simply counting the edges: if the count is not exactly `n - 1`, the answer is immediately false, with no traversal needed. If the count matches, connectivity becomes the only remaining question, because a graph with exactly `n - 1` edges that is fully connected cannot also contain a cycle: removing any single edge would disconnect something, which is only possible if every edge was load-bearing. So a single traversal (depth-first or breadth-first search) from any starting node, or a pass of Union-Find over every edge, confirms whether all `n` nodes end up reachable or joined into one component.

## Solution

```typescript
function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) {
    return false; // a tree on n nodes has exactly n - 1 edges
  }

  const parent = Array.from({ length: n }, (_, i) => i);

  function find(node: number): number {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]); // path compression: point directly at the root
    }
    return parent[node];
  }

  for (const [a, b] of edges) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) {
      return false; // already in the same component: this edge would create a cycle
    }
    parent[rootA] = rootB;
  }

  return true;
}
```

## Complexity

- **Time:** O(V + E). Building the adjacency structure and performing one traversal, or a near-linear Union-Find pass over the edges.
- **Space:** O(V + E). For the adjacency list or Union-Find parent array and visited tracking.

## Watch out for

- Check the edge count before or alongside connectivity; connectivity alone does not rule out an extra edge creating a cycle.
- With Union-Find, a union operation whose two endpoints already share a root is a direct cycle signal.
- A single node with no edges (`n = 1`) is a valid, trivial tree.

## Pattern

This edge-count-plus-connectivity invariant is the standard tree-validation check, closely related to Number of Connected Components and Union-Find-based cycle detection elsewhere in graph problems.

---

Canonical URL: https://www.marauderbot.com/questions/graph-valid-tree
