Graph Valid Tree

MediumGraphsDFSBFSGraphUnion Find

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

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.

Related questions