NUHMAN.com

Introduction

LeetCode 261: Graph Valid Tree challenges us to determine whether a given undirected graph is a valid tree. A tree is defined as a connected graph with no cycles.

This problem is a blend of graph theory and implementation. It’s commonly solved using:

• Union-Find (Disjoint Set)
• Depth-First Search (DFS)

Problem Statement

You are given n nodes labeled from 0 to n - 1 and a list of edges where each edge is a pair of nodes. Return True if the edges make up a valid tree.

Constraints:

• There are no duplicate edges.
• The graph is undirected.

Examples

python

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: True

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: False  # Contains a cycle

✅ Step-by-Step Approach 1: Union-Find (Disjoint Set)

Key Idea

For a graph to be a valid tree:

1. It must be connected.
2. It must have no cycles.
3. It must have exactly n - 1 edges.

Union-Find Code in Python

python

def validTree(n: int, edges: list[list[int]]) -> bool:
    if len(edges) != n - 1:
        return False  # A tree must have exactly n-1 edges

    parent = [i for i in range(n)]

    def find(x):
        while x != parent[x]:
            parent[x] = parent[parent[x]]  # Path compression
            x = parent[x]
        return x

    def union(x, y):
        rootX, rootY = find(x), find(y)
        if rootX == rootY:
            return False  # Found a cycle
        parent[rootY] = rootX
        return True

    for u, v in edges:
        if not union(u, v):
            return False

    return True

🔍 Explanation of Union-Find

• Initialization: Every node is its own parent.
• Find: Locate the root of a node with path compression.
• Union: Connect two components, but return False if they’re already connected (cycle).
• Edge Count Check: A valid tree has exactly n - 1 edges.

✅ Step-by-Step Approach 2: DFS for Cycle Detection + Connectivity

python

from collections import defaultdict

def validTree(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):
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if not dfs(neighbor, node):
                return False
        return True

    return dfs(0, -1) and len(visited) == n

🔍 Explanation of DFS Approach

• Cycle detection: If we revisit a node that’s not the parent → cycle.
• Connectivity: All nodes should be visited from node 0.

🧠 Tree Properties Recap

To validate a graph is a tree:

• Must be connected → All nodes reachable from one node
• Must have no cycles
• Must have n - 1 edges

🧪 Time & Space Complexity

• Time Complexity: O(n) – each edge is checked once
• Space Complexity: O(n) – for parent array or visited set

✅ Conclusion

LeetCode 261 tests core graph theory knowledge:

• What makes a tree?
• How to detect cycles?
• How to check connectivity?

Union-Find is typically faster for dense graphs.

DFS is more intuitive for learning purposes.

This problem sets a great foundation for:

• Detecting cycles
• Connected components
• Spanning trees