Overview

Given n nodes labeled from 0 to n - 1 and a list of undirected edges, determine if these edges form a valid tree.

A valid tree must satisfy:

1. It is connected — all nodes are reachable from any node.
2. It has no cycles.

An equivalent check: a graph with n nodes is a tree if and only if it is connected and has exactly n - 1 edges.

Constraints

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length === 2
• 0 <= edges[i][0], edges[i][1] < n
• No duplicate edges.

Examples

isTree(5, [[0,1], [0,2], [0,3], [1,4]]);
// => true
//    0
//   /|\
//  1 2 3
//  |
//  4

isTree(5, [[0,1], [1,2], [2,3], [1,3], [1,4]]);
// => false  (cycle: 1-2-3-1)

isTree(4, [[0,1], [2,3]]);
// => false  (not connected)

Solution

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

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

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

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

  return true;
}

Resources

• Graph Valid Tree — LeetCode
• Tree (Graph Theory) — Wikipedia