Skip to main content

261. Graph Valid Tree

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 Sam K., Founder, InterviewChamp.AI · Last verified

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.

More Cisco coding interview questions

See all Cisco problems →

Companies that also ask Graph Valid Tree