Graph Valid Tree

Examples

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

Every node is connected, with exactly one path between any two nodes and no cycles.

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

Nodes 1, 2, and 3 form a cycle (1-2, 2-3, 1-3), so this isn't a tree even though every node is reachable.

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

There's no cycle, but the graph is split into two disconnected pieces, so it isn't one single tree.

Constraints

• 1 <= n <= 2000

• 0 <= edges.length <= 5000

• There are no self-loops or duplicate edges.

Approach

First, a quick shortcut: any tree with n nodes must have exactly n - 1 edges. If the given edge count is different, it's immediately not a tree - no further checking needed.

If the edge count does match, that alone isn't proof - you could still have a small cycle in one part of the graph and a disconnected node elsewhere, which also happens to add up to n - 1 edges overall. So you still need to confirm two things: no cycles, and fully connected.

Union-Find checks both at once. Start with every node in its own group. For each edge, try to union its endpoints: if they're already in the same group, this edge would create a cycle - stop and return false. If you make it through every edge without that happening, and the edge count was n - 1, everything must have merged into a single group, so the graph is connected and acyclic: a valid tree.

Solutions

DFS Traversal

Check the edge count is n - 1 first. Then run one DFS from node 0, being careful never to walk immediately back along the edge you just came from (since edges are undirected). If the DFS reaches every node without ever revisiting one another way, and it started with the right edge count, it's a valid tree.

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;

  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const visited = new Set();

  function dfs(node, parent) {
    if (visited.has(node)) return false; // revisiting means a cycle
    visited.add(node);

    for (const neighbor of graph[node]) {
      if (neighbor === parent) continue; // don't walk back along the edge we came from
      if (!dfs(neighbor, node)) return false;
    }
    return true;
  }

  return dfs(0, -1) && visited.size === n;
}

Time: O(V + E) · Space: O(V + E)

Optimal - Union-Find

After confirming the edge count is n - 1, union each edge's endpoints. If any edge connects two nodes already in the same group, that's a cycle, so it can't be a tree. If every edge unions cleanly, the graph is both acyclic and (given the right edge count) fully connected.

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;

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

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  for (const [a, b] of edges) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return false; // cycle

    parent[rootA] = rootB;
  }

  return true;
}

Time: O(n × α(n)) - nearly O(n) · Space: O(n)