Graph Valid Tree

Check whether an undirected graph is a valid tree with no cycles and full connectivity.

graph dfs bfs connectivity cycle-detection

Given an integer `n` (number of nodes labeled from `0` to `n-1`) and a list of undirected edges `edges` (each edge is a list `[u, v]`), write a function `valid_tree(n, edges)` that returns `True` if the graph is a valid tree, and `False` otherwise.

A valid tree must satisfy:
1. It is connected: every node is reachable from every other node.
2. It has no cycles.

**Function signature:** `def valid_tree(n: int, edges: List[List[int]]) -> bool:`

Constraints

`1 <= n <= 2000`
`0 <= len(edges) <= 5000`
Each edge is a list of two distinct integers between `0` and `n-1` inclusive.
There are no duplicate edges.
The graph is undirected.

Your solution should ideally run in O(n + len(edges)) time and O(n) space.

Example

>>> valid_tree(5, [[0,1],[0,2],[0,3],[1,4]])
True
>>> valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]])
False
>>> valid_tree(4, [[0,1],[2,3]])
False

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

For a tree with n nodes, the number of edges must be exactly n-1. If not, the answer is definitely False.

Use a DFS/BFS from node 0 to count visited nodes; the graph is connected if you visit all n nodes.

Additionally, if edges == n-1 and the graph is connected, it automatically has no cycles (a connected graph with n-1 edges is acyclic).

Alternatively, use union-find to detect cycles while connecting nodes.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.