Graph Valid Tree (LeetCode 261)

The problem

You get n nodes labelled 0 to n - 1 and a list of undirected edges. Return True if these edges make the graph a valid tree: every node is connected and there are no cycles. Otherwise return False.

Input:  n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output: True

Input:  n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: False

The first is a tree rooted at 0. The second has the cycle 1 → 2 → 3 → 1.

How to think about it

Start with brute force. Build an adjacency list, run a DFS from node 0, and check two things: you never reach a visited node except through the edge you came by (no cycle), and you reach all n nodes (connected). That works in O(n + E), but the “except the parent” bookkeeping for undirected graphs is fiddly and easy to get wrong.

The key insight: a tree on n nodes has exactly n − 1 edges. That’s a fact worth memorising. It means:

• fewer than n − 1 edges: the graph can’t be connected;
• more than n − 1 edges: there must be a cycle;
• exactly n − 1 edges: it’s a tree if and only if there’s no cycle (or, equivalently, if it’s connected).

So one cheap length check rules out most bad inputs, and then you only need to check for a cycle.

Detect the cycle with union-find. Add edges one at a time. If an edge joins two nodes that already share a root, it closes a cycle: return False. If all n − 1 edges are added without that happening, they merged n singletons into a single group, so the graph is connected too.

Which pattern is this? Union-find for cycle detection on an undirected graph, plus a counting fact about trees. The tell is “is this graph a tree?” or “connected and acyclic”.

Approach

1. If len(edges) != n - 1, return False.
2. Set parent[i] = i for every node.
3. For each edge, find both roots. If they’re equal, return False (cycle).
4. Otherwise union them.
5. If every edge was added cleanly, return True.

Solution

def valid_tree(n, edges):
    if len(edges) != n - 1: return False       # a tree on n nodes has exactly n-1 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              # already connected: this edge makes a cycle
        parent[ra] = rb
    return True                                # n-1 merges, no cycle: one connected tree
# valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]) -> True
# valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]) -> False

Dry run

First example, n = 5, four edges (passes the length check):

No edge closed a cycle, so the answer is True. The second example has 5 edges for 5 nodes and is rejected by the length check before union-find runs.

Complexity

• Time: O(n·α(n)). At most n − 1 edges reach the loop, each with two near-constant find calls.
• Space: O(n) for parent.

Edge cases and pitfalls

• One node, no edges is a valid tree: 0 == 1 - 1, and the loop never runs.
• Right edge count but disconnected with a cycle, e.g. n = 4, [[0,1],[1,2],[0,2]]: the edge (0, 2) closes a cycle and the answer is False. With n − 1 edges, a cycle and disconnection always go together, so checking one is enough.
• Skipping the length check. Without it, a forest like n = 4, [[0,1]] has no cycle and would wrongly return True.
• DFS without tracking the parent reports every undirected edge as a cycle, since a → b → a looks like a revisit.

Related problems

• Redundant Connection (LeetCode 684): find the edge that turns a tree into a graph with a cycle.
• Number of Connected Components (LeetCode 323): count the groups that union-find leaves.
• Course Schedule (LeetCode 207): cycle detection on a directed graph, which needs a different tool.