Graph Valid Tree - Solution & Explanation
Problem Statement
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.
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
Constraints:
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= ai, bi < nai != bi- There are no self-loops or repeated edges.
Approach Overview
Problem Overview: You are given n nodes labeled from 0 to n-1 and a list of undirected edges. The task is to determine whether these edges form a valid tree. A graph is a tree only if it is fully connected and contains no cycles. That means every node must be reachable from any other node, and the total number of edges must be exactly n - 1.
Approach 1: Union-Find (Disjoint Set) (O(n) time, O(n) space)
This approach uses the Union Find data structure to track connected components while processing edges. Start with each node in its own set. For every edge (u, v), check whether both nodes already belong to the same set using find(). If they do, adding the edge would create a cycle, so the graph cannot be a valid tree. Otherwise, merge the two sets using union(). A quick pre-check helps: a valid tree must have exactly n - 1 edges. If the edge count differs, return false immediately. Union-Find is efficient because path compression and union-by-rank keep operations nearly constant time. The overall complexity is O(n) time and O(n) space.
Approach 2: Depth-First Search (DFS) Traversal (O(n) time, O(n) space)
This method treats the problem as a graph traversal using Depth-First Search. First build an adjacency list from the edge list so you can quickly access neighbors of each node. Start DFS from node 0 and keep track of visited nodes. While exploring neighbors, ignore the node you came from (the parent) to avoid falsely detecting a cycle in an undirected graph. If DFS reaches a node that was already visited through another path, a cycle exists and the graph is not a valid tree. After traversal finishes, verify that all nodes were visited. If some nodes remain unvisited, the graph is disconnected. DFS visits each node and edge once, giving O(n) time and O(n) space due to recursion and adjacency storage. A similar strategy works with Breadth-First Search.
Recommended for interviews: Union-Find is often the expected solution because it directly models the two properties of a tree: no cycles and a single connected component. The n - 1 edge rule quickly filters invalid cases, and cycle detection becomes a constant-time check with find(). DFS demonstrates strong graph fundamentals and works well when you already need an adjacency list for traversal problems. Showing both approaches signals that you understand both connectivity checks and graph traversal patterns.
Approach 1: Union-Find
To determine whether it is a tree, the following two conditions must be met:
- The number of edges is equal to the number of nodes minus one;
- There is no cycle.
We can use a union-find set to determine whether there is a cycle. We traverse the edges, if two nodes are already in the same set, it means there is a cycle. Otherwise, we merge the two nodes into the same set. Then we decrease the number of connected components by one, and finally check whether the number of connected components is 1.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of nodes.
Code
Python
Java
C++
Go
JavaScript
Approach 2: DFS
We can also use depth-first search to determine whether there is a cycle. We can use an array vis to record the visited nodes. During the search, we first mark the node as visited, then traverse the nodes adjacent to this node. If the adjacent node has been visited, we skip it, otherwise we recursively visit the adjacent node. Finally, we check whether all nodes have been visited. If there are nodes that have not been visited, it means that it cannot form a tree, so we return false.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Code
Python
Java
C++
Go
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Union-Find | — |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n) | O(n) | Best general solution for detecting cycles and connectivity while processing edges |
| Depth-First Search (DFS) | O(n) | O(n) | Useful when adjacency lists are already built or when practicing graph traversal patterns |
| Breadth-First Search (BFS) | O(n) | O(n) | Alternative traversal approach when iterative queue-based graph exploration is preferred |
Video Solution
Graph Valid Tree - Leetcode 261 - Python • NeetCode • 168,674 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Graph Valid Tree easy or hard?
Graph Valid Tree Python/Java solution
How to solve Graph Valid Tree in O(n)?
What is the best approach for Graph Valid Tree?
Is Graph Valid Tree asked at Google/Amazon/Meta?
What data structure is used in Graph Valid Tree?
What is the time complexity of Graph Valid Tree?
Ready to solve this problem?
Practice Graph Valid Tree with our built-in code editor and test cases.
Practice on FleetCode