Graph Valid Tree

Problem

You have a graph of n nodes labeled from 0 to n - 1. Given an integer n and a list of edges, return true if and only if it is a valid tree.

Examples

The brute-force approach

Check two conditions: (1) exactly n-1 edges, (2) no cycle via DFS. If either fails, return false.

if len(edges) != n - 1: return False
adj = defaultdict(list)
for a, b in edges:
    adj[a].append(b); adj[b].append(a)
visited = set()
def dfs(node, parent):
    visited.add(node)
    for nei in adj[node]:
        if nei == parent: continue
        if nei in visited: return False
        if not dfs(nei, node): return False
    return True
return dfs(0, -1) and len(visited) == n

O(V + E) — actually fine. Union-Find is slightly cleaner for this "is it a tree?" check.

Spotting the pattern

This is a Union-Find problem. The key question to ask yourself:

A tree with n nodes always has exactly how many edges? How does that condition alone eliminate some invalid cases before you even check for cycles?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.