You are given n nodes labeled 0 to n - 1 and a list of undirected edges. Return true if the edges form a valid tree: connected, and with no cycle. A single node with no edges is a tree.
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: 1-2-3 closes a cycle.
Example 3:
Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: acyclic but disconnected — a forest, not a tree.
Example 4:
Input: n = 1, edges = []
Output: true
Constraints
1 <= n <= 2000
0 <= edges.length <= 5000
No self-loops or duplicate edges.
Prerequisites
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. Count the Edges, Then Check Connectivity Optimal
Intuition
A tree on n nodes has exactly n-1 edges — that single check does half the work, because fewer means disconnected and more guarantees a cycle. With the count right, connectivity is the only remaining question, and connected plus n-1 edges IMPLIES acyclic. Union-find answers both in one pass: a union that finds both nodes already joined is a cycle.
Algorithm
1. Reject immediately unless there are exactly n-1 edges. 2. Union each edge; an edge whose endpoints already share a root closes a cycle. 3. Everything ending in one component is a tree.
Time & Space
Time near O(n + edges) with path compression. Space O(n).