medium

Graph Valid Tree

Check whether a given set of edges and nodes forms a valid tree.

1. Define the problem

Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and edges where edgesi = [ai, bi] indicates an undirected edge between nodes ai and bi. Return true if the edges form a valid tree , or false otherwise. A valid tree has exactly n - 1 edges and no cycle. Check the edge count first, then union every edge — any edge whose endpoints already share a root closes a cycle.

Constraints

  • 1 ≤ n ≤ 2000
  • 0 ≤ edges.length ≤ 5000
  • edgesi.length == 2
  • 0 ≤ ai, bi < n
  • ai != bi

Example

Inputn = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Outputtrue

Explanation Four edges connect all five nodes with no cycle — this is a valid tree.

2. Know the words first

In plain terms

Valid tree
A connected graph with no cycles — every node reachable from every other, with no redundant edge.
3. Visualize the solution

Check the edge count, then union edges watching for a cycle

Check the edge count, then union edges watching for a cycle
Statusunion

edges.length = 4 = n - 1, so the count check passes. Union edge [0, 1].

What happens in this step

edge [0, 1]
find(0) → 0   find(1) → 1
roots differ → union: parent[0] = 1
parent array: [0, 1, 2, 3, 4] → [1, 1, 2, 3, 4]

Nodes 0 and 1 merge, with root 1 now representing both.
Step 1 of 4

Steps to visualize

  1. If edges.length is not exactly n - 1, it cannot be a tree — return false immediately.
  2. Otherwise give every node its own group.
  3. For each edge, compare find on both endpoints; if they already match, a cycle exists — return false.
  4. Otherwise union them and continue.
  5. If every edge unions cleanly, the graph is a valid tree.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Check the edge count, then union edges watching for a cycle
Statusunion

edges.length = 4 = n - 1, so the count check passes. Union edge [0, 1].

What happens in this step

edge [0, 1]
find(0) → 0   find(1) → 1
roots differ → union: parent[0] = 1
parent array: [0, 1, 2, 3, 4] → [1, 1, 2, 3, 4]

Nodes 0 and 1 merge, with root 1 now representing both.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function validTree(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);
    const rootB = find(b);

    if (rootA === rootB) {
      return false;
    }

    parent[rootA] = rootB;
  }

  return true;
}
Time
O(n · α(n))
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]trueexample from the docstring
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]falsetoo many edges for the number of nodes
n = 1, edges = []truea single node with no edges is trivially a valid tree
n = 4, edges = [[0,1],[2,3]]falsenot enough edges to connect every node
n = 4, edges = [[0,1],[1,2],[2,0]]falseedge count matches n - 1, but a cycle exists and one node is isolated
n = 4, edges = [[0,1],[1,2],[2,3]]truea simple chain with no branching is still a valid tree

Keep reading