LeetCode 261 · Union-Find · Graphs

Graph Valid Tree

MediumIs this graph a tree? Exactly n−1 edges and no cycles.
Given n nodes labeled 0..n−1 and a list of undirected edges, determine if these edges make up a valid tree — a graph that is fully connected and contains no cycles.

Walkthrough

try:
A graph is a valid tree iff it has exactly n−1 edges AND no cycles (which then forces it to be connected).
01234
connectingcomponentscycle edge
1
function validTree(n, edges) {
2
  if (edges.length !== n - 1) return false;
◄
3
  const parent = [...Array(n).keys()];
4
  const find = (x) => {
5
    while (parent[x] !== x) x = parent[x];
6
    return x;
7
  };
8
  for (const [u, v] of edges) {
9
    const ru = find(u), rv = find(v);
10
    if (ru === rv) return false;   // cycle
11
    parent[ru] = rv;               // union
12
  }
13
  return true;
14
}
edges = 4n-1 = 4
step 0 / 14
line 2
Edge count: 4 vs n−1 = 4
Exactly 4 edges — the right amount for a tree. Now check there are no cycles.

Intuition

A tree on n nodes always has exactly n − 1 edges. Fewer and it can’t be connected; more and it must contain a cycle. So check the edge count first — it is a free early exit.

With the count right, the only remaining question is whether there is a cycle. Union–Find answers that: keep each node’s component, and join components as you add edges.

If an edge connects two nodes that are ALREADY in the same component, it closes a loop → not a tree.

If all n − 1 edges join two different components, no cycle ever formed — and n − 1 non-redundant merges must leave exactly one component, so it is automatically connected too.

The algorithm

  1. 01If edges.length ≠ n − 1, return false immediately.
  2. 02Initialize Union–Find with each node as its own component.
  3. 03For each edge, find the roots of both endpoints.
  4. 04If the roots match, a cycle exists → return false. Otherwise union the two components.
  5. 05If every edge was absorbed without a cycle, return true.

Reference implementation

1
function validTree(n, edges) {
2
  if (edges.length !== n - 1) return false;   // a tree has exactly n-1 edges
3
  const parent = [...Array(n).keys()];
4
  const find = (x) => {
5
    while (parent[x] !== x) x = parent[x];
6
    return x;
7
  };
8
  for (const [u, v] of edges) {
9
    const ru = find(u), rv = find(v);
10
    if (ru === rv) return false;   // already connected -> cycle
11
    parent[ru] = rv;               // union
12
  }
13
  return true;
14
}

Complexity

Time
O(n · α(n)) ≈ O(n) with Union–Find.
Space
O(n) for the parent array.