Graph Valid Tree

You are given n nodes labelled 0 to n - 1 and a list edges, where each edges[i] = [a, b] is an undirected connection between nodes a and b.

Return true if these edges form a valid tree, and false otherwise. A tree is a graph in which every node can reach every other node (it is connected) and there are no cycles. A single node with no edges counts as a tree.

Example 1

Example 2

Example 3

Constraints

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2 and 0 <= a, b < n
• a != b, and no edge appears twice (in either direction).

Pattern Path · Graphs: Ordering & Union-Find · problem 142 of 169

Start simple

For every edge, remove it and run a BFS to see whether its endpoints are still connected (that would mean a cycle), then check connectivity: O(E·(V + E)) time.

The key idea

Two facts about trees do most of the work. A tree on n nodes always has exactly n - 1 edges. And for a graph with exactly n - 1 edges, being connected and being acyclic are equivalent: adding edges one by one without ever closing a cycle merges two components each time, so n - 1 such merges leave one component.

So first reject any input whose edge count is not n - 1. Then run union-find: start with every node as its own set and, for each edge, look up the roots of both endpoints. If they already share a root, the endpoints were connected before this edge, so the edge closes a cycle and the answer is false. Otherwise merge the two sets. If every edge merges two different sets, the graph is a tree.

A BFS or DFS from node 0 that counts reachable nodes works equally well after the edge-count check: the graph is a tree exactly when all n nodes are reached.

Complexity

• Time: O(n + E·α(n))
• Space: O(n)

Python

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A tree on n nodes has exactly n - 1 edges and no cycles.
        if len(edges) != n - 1:
            return False

        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path halving
                x = parent[x]
            return x

        for a, b in edges:
            root_a, root_b = find(a), find(b)
            if root_a == root_b:
                return False  # a and b are already connected: this edge closes a cycle
            parent[root_a] = root_b
        # n - 1 edges and no cycle means everything was merged into one component.
        return True

JavaScript

var validTree = function(n, edges) {
  // A tree on n nodes has exactly n - 1 edges and no cycles.
  if (edges.length !== n - 1) return false;

  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };

  for (const [a, b] of edges) {
    const rootA = find(a), rootB = find(b);
    if (rootA === rootB) return false; // this edge closes a cycle
    parent[rootA] = rootB;
  }
  // n - 1 edges and no cycle means everything was merged into one component.
  return true;
};

What the interviewer is checking

The interviewer wants you to state the definition of a tree precisely, notice the n - 1 edge shortcut, and implement union-find or a traversal without bugs.

Mistakes to avoid

• Checking only for cycles: a forest of several separate trees has no cycle but is not a tree.
• Checking only the edge count: n - 1 edges can still hide a cycle plus an isolated node.
• Treating edges as directed, or flagging the edge back to the parent as a cycle in an undirected DFS.

Follow-ups to expect

• Which edge would you remove to make it a tree? (First edge that union-find rejects.)
• How many connected components are there? (Count successful unions: n minus that.)
• What if edges arrive one at a time? (Union-find answers incrementally.)

In real software

Network design tools check that a set of links forms a spanning tree (no loops, everything reachable), which is exactly what protocols like Spanning Tree enforce on Ethernet switches.

Practice next