# LeetCode 261: Graph Valid Tree — Step-by-Step Visual Trace

**Medium** — Graph | DFS | Tree | Union Find

## The Problem

Given n nodes and a list of undirected edges, determine if the edges form a valid tree. A valid tree must be connected and have exactly n-1 edges with no cycles.

## Approach

First check if the number of edges equals n-1, which is a necessary condition for a tree. Build an adjacency list representation of the graph, then perform DFS from node 0 to detect cycles and check connectivity. The graph is a valid tree if no cycles are found during DFS and all nodes are visited.

**Time:** O(n + m) · **Space:** O(n + m)

## Code

```python
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node, parent):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor != parent:
                    if neighbor in visited or not dfs(neighbor, node):
                        return False
            return True

        # Check if the graph is connected
        if not dfs(0, -1):
            return False

        return len(visited) == n
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0261_graph-valid-tree)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0261_graph-valid-tree) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*