MediumNo. 0261LeetCode Premium
Graph Valid Tree — LeetCode 261 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph
- On study lists
- Blind 75 and NeetCode 150
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
- Output
- true
Python solution
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
for a, b in edges:
pa, pb = find(a), find(b)
if pa == pb:
return False
p[pa] = pb
n -= 1
return n == 1Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)where n is the number of nodes
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 261. Graph Valid Tree is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
Frequently asked questions
- How hard is LeetCode 261. Graph Valid Tree?
LeetCode 261. Graph Valid Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 261. Graph Valid Tree?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 261. Graph Valid Tree?
The Python solution on this page uses O(n), where n is the number of nodes auxiliary space.
- What topics does LeetCode 261. Graph Valid Tree cover?
LeetCode 261. Graph Valid Tree is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.
- Is LeetCode 261. Graph Valid Tree a premium problem?
Yes. LeetCode 261. Graph Valid Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.