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 Sam K., 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

More Graphs practice problems

See all Graphs problems →