LeetCode 261 · Graphs

Graph Valid Tree, explained with a picture

Is this network a tree?.

MediumGraphs
▶ Watch it step by step

The problem

Given n nodes and a list of undirected edges, decide whether they form a valid tree: everything connected and no loops.

Input:  n = 5, edges 0-1, 0-2, 0-3, 1-4
Output: true

Picture it

Picture a network of computers. A tree has exactly n − 1 cables and no cable joins two computers that are already connected. We add cables one by one with union-find: any cable that links two already-connected computers makes a loop. At the end everything must be one group.

How to recognise it

  • The question asks whether an undirected graph is a tree: connected, with no loops.
  • A tree on n nodes has exactly n − 1 edges, which gives a cheap first test.
  • Edges can be added one at a time, and a loop appears when an edge joins two nodes that are already connected.
  • n up to 2,000 and 5,000 edges is small, but the check should stay linear for much larger inputs.

Start with brute force

Check the edge count, then check connectivity the long way: from every node, search the graph and confirm all n nodes are reached.

def valid_tree_brute(n, edges):
    if len(edges) != n - 1:
        return False
    adj = defaultdict(list)
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    for s in range(n):
        seen, st = {s}, [s]
        while st:
            x = st.pop()
            for y in adj[x]:
                if y not in seen:
                    seen.add(y)
                    st.append(y)
        if len(seen) != n:
            return False
    return True

Each of n searches costs O(V + E), so time is O(V·(V + E)): about 1.4 × 10^7 for 2,000 nodes and 5,000 edges, and 10^10 for 10^5 of each. Space is O(V + E). (A single search from node 0 would already be O(V + E) and also works; the point here is that union-find answers the same question with no search at all.)

From brute force to the idea

  1. Find the waste. With n − 1 edges, connected and acyclic are equivalent, so you need to check only one of them. Searching from every node checks connectivity again and again.
  2. Count the edges first. If len(edges) != n - 1, return False at once. Too few edges cannot connect n nodes, and too many must contain a loop.
  3. Then look only for loops. With exactly n − 1 edges, a graph with no loop must be connected. Walk the edges and keep groups with union-find.
  4. Detect a loop at the moment it forms. If both ends of an edge already have the same root, the edge closes a loop, so return False. Otherwise link the roots with parent[rb] = ra.
  5. Finish. If every edge merged two different groups, there are n − 1 merges, which leaves one group: a tree.

The key idea: n − 1 edges and no loop together imply a tree.

The key idea

A tree ⇔ exactly n − 1 edges and no union fails (no cycle).

Python solution

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    parent = list(range(n))
    def find(x):
        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          # a loop
        parent[rb] = ra           # union
    return True    # n-1 edges, no loop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(V·(V + E)): a full search from every nodeO(V + E): adjacency lists and a seen set
Union-find (shown code)O(V + E log V) at worst, close to O(V + E) in practice, because path halving keeps chains shortO(V): the parent list

Edge cases

  • One node, no edges (n = 1, []): returns True.
  • Zero nodes (n = 0): returns False, because the edge count of 0 differs from −1.
  • A self-loop (n = 2, [[0,0]]): the count matches, but the edge finds equal roots, so the result is False.
  • Duplicate edges (n = 3, [[0,1],[0,1]]): returns False, because the second edge closes a loop.
  • A loop plus an isolated node (n = 4, [[0,1],[1,2],[2,0]]): returns False.
  • Disconnected with the wrong count (n = 4, [[0,1],[2,3]]): returns False at the first line, because 2 ≠ 3.

Common mistakes

  • Skipping the edge-count test, so a disconnected, loop-free graph such as two separate pairs is accepted.
  • Testing only connectivity and ignoring loops.
  • Linking nodes instead of roots (parent[b] = a).
  • Using < or > for the edge count instead of exact equality.
  • Forgetting that the node count n can include nodes that appear in no edge.
Your turn: is it a forest?

A forest is a graph with no loops, and it may be disconnected. Return whether the given graph is a forest. Describe what changes, then write it if you like.

Compare with our answer

Drop the edge-count test, because a forest can have fewer than n − 1 edges. The loop check stays the same.

def is_forest(n, edges):
    parent = list(range(n))
    def find(x):
        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
        parent[rb] = ra
    return True

is_forest(4, [[0,1],[2,3]]) is True, while valid_tree(4, [[0,1],[2,3]]) is False. Time O(V + E log V), space O(V).

A strong answer mentions: removing the exact edge-count test, keeping the loop detection, and that a forest only needs no loops, not connectivity.

Check what stuck

1. You receive a network of 10^5 servers and cables. It is healthy only if every server can reach every other with no redundant cable. Which approach fits best?

2. After the edge count equals n − 1, why is "no failed union" enough to prove the graph is connected?

3. A learner deletes the first two lines (if len(edges) != n - 1: return False). Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.