# LeetCode 261: Graph Valid Tree

## Problem Restatement

We are given:

- An integer `n`
- A list of undirected edges

The graph has nodes labeled from `0` to `n - 1`.

Each edge:

```python
[a, b]
```

means there is an undirected connection between node `a` and node `b`.

We need to return `True` if these edges form a valid tree. Otherwise, return `False`.

A valid tree must satisfy two properties:

| Property | Meaning |
|---|---|
| Connected | Every node can reach every other node |
| No cycle | There is no circular path |

The problem constraints include `1 <= n <= 2000`, `0 <= edges.length <= 5000`, no self-loops, and no repeated edges.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n` nodes and an edge list |
| Output | Boolean |
| Graph type | Undirected |
| Goal | Check whether the graph is exactly one connected acyclic component |

Example function shape:

```python
def validTree(n: int, edges: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
```

This graph is connected and has no cycle.

Answer:

```python
True
```

Example 2:

```python
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
```

There is a cycle:

```text
1 -> 2 -> 3 -> 1
```

Answer:

```python
False
```

Example 3:

```python
n = 4
edges = [[0, 1], [2, 3]]
```

There is no cycle, but the graph is disconnected.

Nodes `0` and `1` form one component.

Nodes `2` and `3` form another component.

Answer:

```python
False
```

## First Thought: DFS Traversal

A tree is a connected graph without cycles.

So one natural method is:

1. Build an adjacency list.
2. Run DFS from node `0`.
3. Detect whether DFS sees a cycle.
4. Check whether all nodes were visited.

This works.

But Union Find gives a compact way to process edges and detect cycles directly.

## Key Insight

A graph with `n` nodes is a tree if it has:

```python
n - 1
```

edges and no cycle.

Why this works:

- If an undirected graph has `n - 1` edges and no cycle, it must be connected.
- If it has fewer than `n - 1` edges, it cannot connect all nodes.
- If it has more than `n - 1` edges, it must contain a cycle.

So we can first check:

```python
len(edges) == n - 1
```

If this is false, return `False`.

Then we only need to detect whether any edge creates a cycle.

Union Find is designed for this.

## Union Find Idea

Initially, every node is its own component.

For example:

```python
n = 5
```

starts as:

```text
{0}, {1}, {2}, {3}, {4}
```

When we process edge `[0, 1]`, we merge the components:

```text
{0, 1}, {2}, {3}, {4}
```

When we process edge `[0, 2]`, we merge again:

```text
{0, 1, 2}, {3}, {4}
```

If an edge connects two nodes already in the same component, then there is already a path between them.

Adding that edge creates a cycle.

So the graph cannot be a tree.

## Algorithm

1. If `len(edges) != n - 1`, return `False`.
2. Create a parent array:
   ```python id="kgzjzi"
   parent[i] = i
   ```
3. For each edge `[a, b]`:
   - Find the root of `a`.
   - Find the root of `b`.
   - If both roots are equal, return `False`.
   - Otherwise, union the two components.
4. Return `True`.

The edge count check handles disconnected graphs.

The Union Find check handles cycles.

## Walkthrough

Use:

```python
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
```

There are `4` edges.

Since:

```python
4 == 5 - 1
```

the edge count is possible for a tree.

Start:

```python
parent = [0, 1, 2, 3, 4]
```

Process `[0, 1]`.

Roots are different, so union them.

Process `[0, 2]`.

Roots are different, so union them.

Process `[0, 3]`.

Roots are different, so union them.

Process `[1, 4]`.

Roots are different, so union them.

No cycle appears.

Because the graph has exactly `n - 1` edges, it is connected.

Return:

```python
True
```

Now use:

```python
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
```

There are `5` edges.

A tree with `5` nodes must have exactly `4` edges.

So we immediately return:

```python
False
```

## Correctness

A valid tree with `n` nodes must have exactly `n - 1` edges. Therefore, if the edge count differs from `n - 1`, the graph cannot be a valid tree.

After passing the edge count check, the algorithm processes each edge with Union Find.

Union Find maintains connected components. If an edge connects two nodes already in the same component, then those nodes already have a path between them. Adding the edge creates a cycle, so the graph cannot be a tree.

If no edge creates a cycle, then the graph is acyclic.

An undirected acyclic graph with `n` nodes and `n - 1` edges is connected. Therefore, after the edge count check and the cycle check both pass, the graph is a valid tree.

Thus the algorithm returns `True` exactly for valid trees.

## Complexity

Let `E` be the number of edges.

| Metric | Value | Why |
|---|---|---|
| Time | `O(E α(n))` | Each Union Find operation is almost constant |
| Space | `O(n)` | Parent and rank arrays |

Here, `α(n)` is the inverse Ackermann function. In practice, it behaves like a small constant.

## Implementation

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

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

            return True

        for a, b in edges:
            if not union(a, b):
                return False

        return True
```

## Code Explanation

First, check the edge count:

```python
if len(edges) != n - 1:
    return False
```

This quickly rejects graphs that are too sparse or too dense to be a tree.

The parent array starts with each node as its own root:

```python
parent = list(range(n))
```

The rank array helps keep the Union Find tree shallow:

```python
rank = [0] * n
```

The `find` function returns the root component of a node:

```python
def find(x: int) -> int:
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
```

The line:

```python
parent[x] = find(parent[x])
```

performs path compression.

That means future lookups become faster.

The `union` function merges two components.

If both nodes already have the same root:

```python
if root_a == root_b:
    return False
```

then the edge creates a cycle.

Otherwise, we attach the smaller-rank tree under the larger-rank tree.

Finally, every edge is processed:

```python
for a, b in edges:
    if not union(a, b):
        return False
```

If no cycle is found, the graph is a valid tree.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
    assert s.validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
    assert s.validTree(4, [[0, 1], [2, 3]]) is False
    assert s.validTree(1, []) is True
    assert s.validTree(2, [[0, 1]]) is True
    assert s.validTree(3, [[0, 1], [1, 2]]) is True
    assert s.validTree(3, [[0, 1], [0, 2], [1, 2]]) is False
    assert s.validTree(4, [[0, 1], [1, 2], [2, 3]]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard valid tree | Connected and acyclic |
| Cycle example | Rejects cycle |
| Disconnected graph | Rejects multiple components |
| Single node | Empty edge list is valid |
| Two connected nodes | Smallest non-trivial tree |
| Simple chain | Valid tree shape |
| Triangle | Cycle detection |
| Longer chain | Connected acyclic graph |