‹ DS&A interview · Socratic
DSA · Graph · #80

Graph Valid Tree

Module 43 · difficulty 3/5·⏱ 30:00starts on first keystroke

You have `n` nodes labeled `0..n-1` and a list of undirected `edges` where `edges[i] = [a, b]` denotes an edge between `a` and `b`. Implement `validTree(n, edges)` that returns `true` if and only if these edges form a **valid tree**. A valid tree is a graph that is **fully connected** (every node reachable from every other) and **contains no cycles**. Equivalently, it has exactly `n - 1` edges, all nodes belong to one connected component, and no edge creates a cycle.

Examples
  • n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → true — Connected, 4 edges for 5 nodes, no cycle.
  • n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] → false — Edge [1,3] closes a cycle 1-2-3-1.
  • n = 4, edges = [[0,1],[2,3]] → false — Two separate components, not fully connected.
Constraints
  • · 1 <= n <= 2000
  • · 0 <= edges.length <= 5000
  • · edges[i].length == 2
  • · 0 <= a, b < n
  • · a != b
  • · There are no duplicate edges.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.