> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Graph Valid Tree Python Solution with Tests

> Tested Python solution for LeetCode 261 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 261, Medium. Topics: Depth-First Search, Breadth-First Search, Union Find, Graph. [View on LeetCode](https://leetcode.com/problems/graph-valid-tree/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 261   # by problem number
lcpy gen -s graph_valid_tree   # by problem name
```

## Problem

Given `n` nodes labeled from `0` to `n-1` and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

### Examples

```
Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true
```

```
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false
```

### Constraints

* 0 \<= n \<= 2000
* 0 \<= edges.length \<= 5000
* edges\[i].length == 2
* 0 \<= ai, bi \< n
* ai != bi
* There are no self-loops or repeated edges.

**Note:** you can assume that no duplicate edges will appear in edges. Since all edges are undirected, \[0,1] is the same as \[1,0] and thus will not appear together in edges.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/graph_valid_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/graph_valid_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def valid_tree(self, n: int, edges: list[list[int]]) -> bool:
        # Edge case: empty graph is a valid tree
        if n == 0:
            return True

        # A valid tree must have exactly n-1 edges
        if len(edges) != n - 1:
            return False

        # Build adjacency list
        graph: list[list[int]] = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # DFS to check connectivity
        visited = set()

        def dfs(node: int) -> None:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        # Start DFS from node 0
        dfs(0)

        # Check if all nodes are visited (connected)
        return len(visited) == n
```

## Complexity

| Time     | Space    |
| -------- | -------- |
| O(n + e) | O(n + e) |

## Tags

[Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).