4.20.12 — Graph Valid Tree

LeetCode 261 · Medium · ★ Blind 75

The problem

Given n nodes and a list of undirected edges, return true if they form a valid tree.

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]   →  true
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]   →  false   (there is a cycle)

In plain English, given N nodes (labeled 0 to N-1) and a list of undirected edges, you must determine if the resulting graph is a valid tree. A valid tree must connect all nodes together and must contain absolutely no cycles.

The pattern

A tree is a graph that is connected and has no cycle. Both conditions, and this problem exists because people check only one.

The ELI5 Analogy

Think of a tree as a family's power strip setup. You have N electronics and you want to plug them all together using extension cords (edges) so that everything gets power from one single wall outlet.

• If you use too few cords, some electronics won't get power (not connected).
• If you use too many cords, you might accidentally plug an extension cord into another extension cord in a circle, creating a dangerous short circuit (a cycle). To perfectly connect N electronics without short circuits, you need exactly N-1 cords. If someone hands you a box of cords and asks, "Will this make a valid power setup?", your very first move should be to just count the cords. If it's not N-1, you say "No!" immediately without even looking at how they plug in.

There is a shortcut that makes it much easier. For a graph with n nodes:

Connected + exactly n − 1 edges ⟹ no cycle.

Why: a connected graph needs at least n − 1 edges to link everything. Any extra edge must join two nodes already connected, which closes a cycle. So with exactly n − 1 edges, connectivity alone rules out cycles.

The same works the other way: acyclic + exactly n − 1 edges ⟹ connected.

So check two things, and one of them is a single comparison:

1. len(edges) == n - 1
2. the graph is connected

Check the edge count first. It is O(1) and it eliminates most invalid inputs before any traversal.

The solution — union-find

Python

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False                      # too few or too many, instantly wrong

        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                  # cycle
            parent[rb] = ra                   # merge

        return True

TypeScript

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;

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

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

  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[rb] = ra;
  }

  return true;
}

With the edge count already checked, there is nothing left to verify at the end. If n − 1 edges all merged two different components, then n − 1 merges happened, and n components reduced by n − 1 leaves exactly one. Connected, automatically.

That is why the loop can return True immediately rather than counting components afterwards.

Union by size is omitted here because path halving alone is fast enough at this size. Include it if asked; it is two extra lines.

The DFS version

def validTree(self, n, edges):
    if len(edges) != n - 1:
        return False

    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)

    seen = set()
    stack = [0]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        stack.extend(adj[node])

    return len(seen) == n          # reached everything → connected

With the edge count already confirmed, the traversal only has to prove connectivity — reach every node from node 0. No cycle check is needed at all.

Without the edge-count shortcut, the DFS would have to detect cycles too, and for an undirected graph that means "I reached an already-visited node that is not the one I came from". Every undirected edge looks like a two-cycle otherwise, so the parent must be excluded:

def dfs(node, parent):
    seen.add(node)
    for nxt in adj[node]:
        if nxt == parent: continue        # the edge we arrived on
        if nxt in seen: return False      # a real cycle
        if not dfs(nxt, node): return False
    return True

That parent check is the undirected cycle rule, and it is different from the three-state rule for directed graphs in 4.20.8. Knowing which applies to which is worth more than either alone.

Edge cases

• n = 1, edges = [] — a single node with no edges is a valid tree. 0 == 1 - 1 ✓.
• n = 0 — arguably a tree, arguably not. Ask; the constraints usually rule it out.
• A duplicate edge [[0,1],[0,1]] — the second one finds both nodes already connected and returns false. Correct: a duplicate edge is a two-node cycle.
• A self-loop [[0,0]] — find(0) == find(0), so false. Also correct.

Code Walkthrough & Trace

n = 4, edges = [[0,1], [1,2], [2,3]] (A line graph, which is a tree)

Step	Check / Action	State
1	len(edges) == 4 - 1?	3 == 3 (True). Continue.
2	Loop edge [0,1]. find(0)=0, find(1)=1.	Not equal. Union.
3	Loop edge [1,2]. find(1)=0, find(2)=2.	Not equal. Union.
4	Loop edge [2,3]. find(2)=0, find(3)=3.	Not equal. Union.
5	End of loop.	Return True.

Complexity

O(n \cdot \alpha(n)), effectively O(n), with O(n) space. The edge count check makes the whole thing O(1) for most invalid inputs. To break it down: we first do an O(1) length check. If we pass, we initialize N elements in the parent array (O(N)). We loop over exactly N-1 edges. For each edge, we do inverse-Ackermann time find and union operations (effectively O(1)). Total time is strictly bounded by O(N). Space complexity is O(N) to store the parent array. No adjacency list or recursion stack is needed.

Where this goes next

• Number of Connected Components — drop the tree requirement and count instead. 4.20.11.
• Redundant Connection — n edges instead of n − 1, so find the one that closes the cycle. 4.20.10.
• Minimum Spanning Tree — build a tree from a weighted graph by adding the cheapest edges that do not close a cycle. Kruskal's algorithm is this loop with the edges sorted first. 4.21.

The n − 1 fact is the common thread, and it is worth carrying: a spanning tree of n nodes always has exactly n − 1 edges, which is why Kruskal's stops after n − 1 successful unions.

What the interviewer will push on

"What makes a graph a tree?" Connected and acyclic. Then give the shortcut: connected plus exactly n − 1 edges implies acyclic.

"Why does the edge count shortcut work?" n − 1 is the minimum for connectivity; any extra edge must close a cycle.

"How do you detect a cycle in an undirected graph with DFS?" Reaching a visited node that is not the parent. Contrast it with the three-state rule for directed graphs.

"What about a self-loop or a duplicate edge?" Both are cycles, and union-find catches both without special handling.

"Is a single node a tree?" Yes, and the arithmetic already agrees.

One thing to volunteer: state the two conditions and the shortcut before writing anything. Most wrong answers to this problem check connectivity and forget cycles, or the reverse — saying both up front shows you know why the shortcut is safe.

Next: 4.20.13 Word Ladder — the hardest problem in this chapter, where the graph is never built at all.