Graph Valid Tree
You are given n nodes labeled from:
0 to n - 1
and a list of undirected edges.
Determine whether the graph forms a valid tree.
A graph is a valid tree if:
- All nodes are connected.
- There are no cycles.
Example
n = 5
edges:
0 - 1
0 - 2
0 - 3
1 - 4
Graph:
2
|
4 - 1 - 0 - 3
All nodes are connected and there is no cycle.
Therefore:
true
Important Observation
A tree with n nodes must contain exactly:
n - 1 edges
So we can immediately reject the graph if:
edges.length != n - 1
Then we only need to check connectivity.
Example 1
Input
5 4 0 1 0 2 0 3 1 4
Output
true
Explanation
There are 5 nodes and 4 edges.
n - 1 = 5 - 1 = 4
The graph is:
2
|
4 - 1 - 0 - 3
Every node can be reached from node 0, and there is no cycle.
Therefore, the graph is a valid tree.
Example 2
Input
5 5 0 1 0 2 0 3 1 4 2 4
Output
false
Explanation
There are 5 nodes but 5 edges.
A tree with 5 nodes must contain exactly 4 edges.
Also, the graph contains a cycle:
0 → 1 → 4 → 2 → 0
Therefore, it is not a valid tree.
Constraints
Hints:
Hint 1
A tree with n nodes must have exactly:
n - 1 edges
Hint 2
Build an adjacency list and start DFS/BFS from node 0.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 16, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output