# Graph Valid Tree

- **Canonical ID**: `graph-valid-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/graph-valid-tree
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/graph-valid-tree/

## 1. Core Invariant / The Trick

Graph theorem: an undirected graph on `n` vertices is a tree iff `len(edges) == n - 1` AND union-find joins all edges without ever seeing an internal cycle (`find(u) == find(v)`).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N * a(N))`
- **Space Complexity**: `O(N)`
- **Proof**: Fail-fast `len(edges) != n - 1` rejects disconnected forests and multi-edge graphs immediately in O(1); verifying no cycles in `n - 1` unions proves 1 connected component.

## 3. Minimal Idiomatic Code

### Python
```python
def validTree(n: int, edges: list[list[int]]) -> bool:
    if len(edges) != n - 1:
        return False
    parent = list(range(n))
    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False
        parent[rv] = ru
    return True
```

### TypeScript
```typescript
export function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  for (const [u, v] of edges) {
    const ru = find(u), rv = find(v);
    if (ru === rv) return false;
    parent[rv] = ru;
  }
  return true;
}
```

### C++
```cpp
bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; };
    for (auto& e : edges) {
        int a = find(e[0]), b = find(e[1]);
        if (a == b) return false;
        p[b] = a;
    }
    return true;
}
```

### Java
```java
boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) p[i] = i;
    for (int[] e : edges) {
        int a = find(p, e[0]), b = find(p, e[1]);
        if (a == b) return false;
        p[b] = a;
    }
    return true;
}
int find(int[] p, int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
```

### Go
```go
func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 { return false }
    p := make([]int, n)
    for i := range n { p[i] = i }
    find := func(x int) int { for p[x] != x { p[x] = p[p[x]]; x = p[x] }; return x }
    for _, e := range edges {
        a, b := find(e[0]), find(e[1])
        if a == b { return false }
        p[b] = a
    }
    return true
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Checking only cycle freedom passes disconnected forests like `[0-1, 2-3]` on `n=4` unless `len(edges) == n - 1` or `components == 1` is also enforced.

### Follow-ups
- Rooted tree equivalence check via DFS passing `(node, parent)` instead of DSU.