261. Graph Valid Tree

Given n nodes labeled 0 to n − 1 and a list of undirected edges, return true if the edges form a valid tree.

BFS from 0. Reaching an already-seen node that is not the node we came from means a cycle. At the end, every node must be seen.

1function validTree(n: number, edges: number[][]): boolean {
2  const adj: number[][] = Array.from({ length: n }, () => []);
3  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
4  const parent = new Map([[0, -1]]), queue = [0];
5  while (queue.length) {
6    const u = queue.shift()!;
7    for (const v of adj[u]) {
8      if (v === parent.get(u)) continue;
9      if (parent.has(v)) return false;
10      parent.set(v, u); queue.push(v);
11    }
12  }
13  return parent.size === n;
14}

graph

queue

Build the adjacency list.

1 / 0

Space: play/pause · ←/→: step