29. Graph Valid Tree

mediumAsked at Spotify

Determine whether n nodes and given edges form a valid tree — union-find cycle detection that Spotify applies when validating artist-collaboration graphs to ensure no circular attribution loops exist.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given n nodes labeled 0 to n-1 and a list of undirected edges, write a function to check whether these edges make up a valid tree. A valid tree must be fully connected and have no cycles.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi, no self-loops, no repeated edges

Examples

Example 1

Input

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output

true

Example 2

Input

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

Output

false

Explanation: Cycle between 1-2-3.

Approaches

1. DFS connectivity + cycle check

Build adjacency list; DFS from node 0 tracking the parent to avoid false cycle from undirected back-edge. Confirm all n nodes visited.

Time: O(V + E)
Space: O(V + E)

function validTree(n, edges) {
  if (edges.length !== n - 1) return false; // Fast pre-check
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Set();
  const dfs = (node, parent) => {
    visited.add(node);
    for (const nei of adj[node]) {
      if (nei === parent) continue;
      if (visited.has(nei)) return false;
      if (!dfs(nei, node)) return false;
    }
    return true;
  };
  return dfs(0, -1) && visited.size === n;
}

Tradeoff:

2. Union-Find

Initialise n disjoint sets; for each edge, union the two endpoints. If they already share a root, a cycle is detected. A valid tree also requires exactly n-1 edges.

Time: O(n * alpha(n)) ≈ O(n)
Space: O(n)

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; };
  const union = (a, b) => {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
    return true;
  };
  for (const [a, b] of edges) {
    if (!union(a, b)) return false;
  }
  return true;
}

Tradeoff:

Spotify-specific tips

The fast pre-check — a valid tree on n nodes has exactly n-1 edges — earns immediate positive signal at Spotify. It shows you think about invariants before writing a single loop. The Union-Find solution is preferred in follow-up discussion because it scales to Spotify's graph sizes and is the foundation of the Kruskal's MST algorithm they use in clustering.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Graph Valid Tree and other Spotify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →