Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Graph Valid Tree

LeetCode #261Medium
Connected + exactly n−1 edges + no cycle

Given n nodes and a list of undirected edges, determine whether the edges form a valid tree, meaning the graph is fully connected and contains no cycles.

Asked atAmazonGoogleMeta
step 1 / 21
candidate graph
0
1
2
3
4
call stack
(empty)
Edge-count gate + DFS cycle/connectivity check
▸
1if edges.length != n - 1: return false   // too few/many
2visited = {}
3dfs(u, parent):
4    mark u visited
5    for v in adj[u]:
6        if v == parent: continue          // skip back-edge
7        if v in visited: return false      // cycle!
8        if not dfs(v, u): return false
9    return true
10return dfs(0, none) and visited.size == n // connected
state
  • n5
  • edges4
  • needconnected + acyclic

line 1Graph Valid Tree (LeetCode 261): given n nodes and a list of undirected edges, is the graph a valid tree? A tree is exactly: fully CONNECTED and ACYCLIC. Two equivalent quick conditions — (1) edge count == n − 1, and (2) one DFS reaches all n nodes with no cycle. We check both.