261. Graph Valid Tree

Q: Why are n-1 edges + cycle-free enough?

Because in a graph with n-1 edges, being acyclic is equivalent to being connected. If you have n-1 edges and ANY connected component is missing nodes, another component must have a cycle (pigeonhole: c components on n nodes have at least n-c edges to span — if n-1 edges total and c > 1, some component has more than its spanning tree's worth, i.e., a cycle). So the two-property check is sufficient.

mediumAsked at Cisco

Graph Valid Tree at Cisco asks whether an undirected graph is a tree. The interviewer is checking whether you remember the TWO defining properties — exactly n-1 edges AND fully connected — and whether you reach for Union-Find or DFS to verify them.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite Graph Valid Tree as a 30-minute union-find round.
Blind (2025-10)— Cisco interview thread lists this as a recurring problem for backend / network roles.

Problem

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no self-loops or 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: Contains a cycle 1-2-3-1.

Approaches

1. DFS / BFS connectivity + cycle check

Build adjacency list. DFS from node 0 tracking parent. If we ever visit a node already visited AND it isn't the parent of the current edge, that's a cycle. After DFS, check that we visited all n nodes.

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

function validTreeDFS(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const visited = new Array(n).fill(false);
  function dfs(node, parent) {
    visited[node] = true;
    for (const nb of graph[node]) {
      if (nb === parent) continue;
      if (visited[nb]) return false;
      if (!dfs(nb, node)) return false;
    }
    return true;
  }
  if (!dfs(0, -1)) return false;
  return visited.every(v => v);
}

Tradeoff: Two checks in one pass — cycle detection during DFS, connectivity check by counting visited nodes. The parent-skip in undirected DFS is the gotcha; without it, every edge looks like a back-edge.

2. Union-Find with edge count check (optimal)

Tree has exactly n-1 edges AND is acyclic AND is connected. If edges.length !== n - 1 return false immediately. Otherwise union all edges; if any union returns 'already in same set' that's a cycle.

Time: O((V + E) * alpha(n))
Space: O(V)

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb;
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra;
    else { this.parent[rb] = ra; this.rank[ra]++; }
    return true;
  }
}
function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const uf = new UnionFind(n);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return false;
  }
  return true;
}

Tradeoff: The `edges.length !== n - 1` precheck does most of the work — any tree has EXACTLY n-1 edges, so any other count immediately disqualifies. The union-find then just verifies the remaining cycle-free property; if all unions succeed without a 'same set' rejection, the graph is acyclic AND with n-1 edges that means connected too. Two checks collapse into one elegant test.

Cisco-specific tips

Cisco interviewers grade this on whether you state the TREE DEFINITION upfront: 'A tree on n nodes has EXACTLY n-1 edges, is connected, and is acyclic.' Note that 'n-1 edges + connected' implies acyclic, and 'n-1 edges + acyclic' implies connected — so you only need to verify TWO of the three properties. The union-find solution exploits this: precheck edges = n-1, then verify acyclic via union. Elegant.

Common mistakes

Forgetting the `edges.length === n - 1` check — without it, the DFS variant has to verify connectivity separately and the union-find has to detect both 'too few edges = disconnected' and 'extra edge = cycle' as separate failure modes.
Forgetting the parent-skip in undirected DFS — every back-edge to the parent looks like a cycle.
Off-by-one: tree on n nodes has n-1 edges, not n.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

Number of Connected Components (LC 323) — same union-find scaffold, count instead of true/false.
Redundant Connection (LC 684) — find the edge that creates a cycle.
Minimum Spanning Tree (Kruskal's) — repeated union-find calls choosing cheapest edges.
What if the graph is directed? (Now it's a DAG check + 'exactly one root' check.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why are n-1 edges + cycle-free enough?

Because in a graph with n-1 edges, being acyclic is equivalent to being connected. If you have n-1 edges and ANY connected component is missing nodes, another component must have a cycle (pigeonhole: c components on n nodes have at least n-c edges to span — if n-1 edges total and c > 1, some component has more than its spanning tree's worth, i.e., a cycle). So the two-property check is sufficient.

Union-find or DFS?

Union-find is the cleaner code for this problem (the n-1 precheck collapses two properties into one) and generalizes to dynamic-edge scenarios. DFS is fine and reads more naturally. Cisco interviewers accept both — pick the one you can write without bugs under pressure.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →