This problem follows the Union-Find / DFS pattern, commonly found in the Graphs category. Recognizing this pattern is key to solving it efficiently in an interview setting.
A valid tree has n-1 edges and is connected. Use union-find to check for cycles.
Two conditions define a tree: n-1 edges (no extra) and connected (no missing). Union-Find checks both: edge count + no cycles = tree.
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
def union(x, y):
px, py = find(x), find(y)
if px == py: return false # cycle
parent[px] = py
return true
return all(union(a, b) for a, b in edges)Practice Graph Valid Tree and similar Graphs problems with flashcards. Build pattern recognition through active recall.
Practice this problem