Graph Valid Tree
01 · 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.
A valid tree must satisfy two conditions:
- The graph is fully connected (there is a path between every pair of nodes).
- The graph has no cycles.
02 · Examples
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
true
The 5 nodes are all connected through node 0, and there are exactly 4 edges (n-1), forming a valid tree with no cycles.
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
false
Nodes 1, 2, and 3 form a cycle (1-2-3-1). A tree cannot contain any cycles.
n = 4, edges = [[0,1],[2,3]]
false
The graph is disconnected — nodes {0,1} and {2,3} are in separate components. A tree must be a single connected component.
03 · Constraints
- 011 <= n <= 2000
- 020 <= edges.length <= 5000
- 03edges[i].length == 2
- 040 <= ai, bi < n
- 05ai != bi
- 06There are no self-loops or repeated edges.
04 · Optimal complexity
- Time
- O(V + E)
- Space
- O(V)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.