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:

[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:

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

Input and Output

Example function shape:

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

Examples

Example 1:

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

This graph is connected and has no cycle.

Answer:

True

Example 2:

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

There is a cycle:

1 -> 2 -> 3 -> 1

Answer:

False

Example 3:

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:

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:

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:

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:

n = 5

starts as:

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

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

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

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

{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:

   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:

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

There are 4 edges.

Since:

4 == 5 - 1

the edge count is possible for a tree.

Start:

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:

True

Now use:

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:

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.

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

Implementation

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:

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:

parent = list(range(n))

The rank array helps keep the Union Find tree shallow:

rank = [0] * n

The find function returns the root component of a node:

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

The line:

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:

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:

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

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

Testing

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: