Skip to main content

261. Graph Valid Tree

medium

Given n nodes and a list of edges, decide whether they form a valid tree. A tree is a connected acyclic graph — two conditions that map exactly to one Union-Find pass or one DFS with a parent pointer.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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: The edge [1,3] forms a cycle with [1,2]-[2,3].

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A tree on n nodes has exactly n - 1 edges. Check that first — wrong count is an immediate false.

Hint 2

Then check connected + acyclic. Both conditions hold if and only if a DFS from node 0 visits all n nodes without ever revisiting through a non-parent edge.

Hint 3

Union-Find shortcut: if you ever try to union two nodes already in the same component, that's a cycle — return false. If the edge count is n - 1 and no cycle, the graph is automatically connected.

Solution approach

Reveal approach

Two pieces have to hold: exactly n - 1 edges, and no cycle. If edges.length != n - 1 return false immediately. Then run Union-Find: initialize parent[i] = i. For each edge (u, v), find(u) and find(v); if equal, return false (cycle). Else union them. If you survive all edges, return true — the edge-count check guarantees the graph is connected (n - 1 edges with no cycles on n nodes implies one component). The DFS alternative: do a DFS from node 0 tracking the parent of each call; if you ever see a visited neighbor that isn't the parent, return false. After DFS, return visited.size == n. Both are O((V + E)·alpha(V)) or O(V + E).

Complexity

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

Related patterns

  • union-find
  • dfs
  • bfs
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Graph Valid Tree and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →