LeetCode 261: Graph Valid Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 261: Graph Valid Tree?

In LeetCode 261: Graph Valid Tree, you’re given an integer n (number of nodes, labeled 0 to n-1) and a list of edges (pairs of nodes). Your task is to return true if these edges form a valid tree—a graph with no cycles and exactly one connected component—and false otherwise. This problem introduces graph theory, related to challenges like LeetCode 207: Course Schedule, but focuses on tree properties.

Problem Statement

• Input: An integer n and a list edges where each edge is a pair [u, v].
• Output: A boolean—true if it’s a valid tree, false if not.
• Rules: A tree has n-1 edges, no cycles, and all nodes connected.

Constraints

• n: 1 to 2000.
• Edges: 0 to 10^4 pairs.
• Node values: 0 to n-1.

Examples

• Input: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
• Output: true (a tree: 0 connects to 1, 2, 3; 1 to 4; no cycles).
• Input: n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
• Output: false (cycle: 1-2-3-1).
• Input: n = 1, edges = []
• Output: true (single node is a tree).

Understanding the Problem: Validating a Tree

To solve LeetCode 261: Graph Valid Tree in Python, we need to confirm two things: the graph has no cycles (no loops) and all n nodes are connected with exactly n-1 edges. A tree is like a family tree—one connected piece with no circular connections. A basic way—checking every edge for loops—works but can be slow. We’ll use two methods: 1. Best Solution (Union-Find with Cycle Detection): O(n) time—fast and efficient. 2. Alternative Solution (DFS with Cycle Detection): O(n + e) time—clear but needs more setup.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Union-Find with Cycle Detection

Why This Is the Best Solution

The Union-Find approach with cycle detection is the top pick for LeetCode 261 because it runs in nearly O(n) time—super quick—and uses a smart system to track connections and spot loops without building a full graph. It’s a neat tool that’s easy to learn once you see it in action, making it perfect for this problem.

How It Works

Picture this solution as organizing a big party: you start with everyone in their own group, then pair people up as edges connect them. If you ever try to pair two people already in the same group, you’ve got a loop—party’s off! Here’s how it works, step-by-step, explained simply:

• Step 1: Set Up Groups:
• Give each node (0 to n-1) its own group—like everyone’s a solo act at first.
• Use a list parent where parent[i] = i (each node points to itself).
• Step 2: Union-Find Basics:
• Find: A function to find the “leader” of a node’s group. If node 1 points to 0, and 0 points to itself, 0’s the leader.
• Union: A function to merge two groups by setting one leader to point to the other.
• Step 3: Process Edges:
• For each edge [u, v]:
• Find the leader of u and v.
• If they’re the same, adding this edge makes a cycle—return false.
• If different, merge their groups (union them).
• Step 4: Check Edge Count:
• A tree needs exactly n-1 edges. If not, it’s not a tree (too few = disconnected, too many = cycles).
• Step 5: Put It Together:
• If no cycles and edge count is right, it’s a valid tree!

It’s like playing matchmaker: connect folks, but if they’re already linked, you’ve got a problem!

Step-by-Step Example

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

• Step 1: Initialize:
• parent = [0, 1, 2, 3, 4] (each node is its own leader).
• Edge count = 4, n-1 = 4 (matches!).
• Step 2: Process Edges:
• [0,1]:
• Find(0) = 0, Find(1) = 1 (different).
• Union: parent[1] = 0, now [0, 0, 2, 3, 4].
• [0,2]:
• Find(0) = 0, Find(2) = 2.
• Union: parent[2] = 0, now [0, 0, 0, 3, 4].
• [0,3]:
• Find(0) = 0, Find(3) = 3.
• Union: parent[3] = 0, now [0, 0, 0, 0, 4].
• [1,4]:
• Find(1) = 0 (1 → 0), Find(4) = 4.
• Union: parent[4] = 0, now [0, 0, 0, 0, 0].
• Step 3: Check:
• No cycles (no same-leader pairs), 4 edges = n-1.
• Result: true.

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

• Step 1: parent = [0, 1, 2, 3, 4], edges = 5 (n-1 = 4, too many, but let’s check).
• Step 2:
• [0,1]: Union, parent[1] = 0, [0, 0, 2, 3, 4].
• [1,2]: Find(1) = 0, Union, parent[2] = 0, [0, 0, 0, 3, 4].
• [2,3]: Find(2) = 0, Union, parent[3] = 0, [0, 0, 0, 0, 4].
• [1,3]: Find(1) = 0, Find(3) = 0 (same), cycle!
• Result: false.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Step 1: Check edge count
        if len(edges) != n - 1:
            return False  # A tree must have exactly n-1 edges

        # Step 2: Set up parent array
        parent = list(range(n))  # Each node starts as its own leader

        # Step 3: Find function to get leader
        def find(x):
            # Keep going up until you find the top leader
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        # Step 4: Union function to merge groups
        def union(x, y):
            parent[find(x)] = find(y)  # Make y’s leader x’s leader

        # Step 5: Process each edge
        for u, v in edges:
            # If u and v already share a leader, adding this edge makes a cycle
            if find(u) == find(v):
                return False
            union(u, v)  # Merge their groups

        # Step 6: No cycles found, edge count matches
        return True

• Time Complexity: O(n)—Union-Find with path compression is nearly linear.
• Space Complexity: O(n)—parent array.

This solution is like a quick group organizer—no loops allowed!

Alternative Solution: DFS with Cycle Detection

Why an Alternative Approach?

The DFS approach explores the graph like a maze, checking for cycles by tracking visited nodes. It’s a bit more work to set up but paints a clear picture of the tree’s shape, making it a nice way to see how graphs connect.

How It Works

Think of this as exploring a cave: start at one spot, mark where you’ve been, and if you ever bump into a spot you’ve already seen (via a different path), there’s a loop. Here’s how it works, step-by-step:

• Step 1: Build the Graph:
• Use a list of lists to store neighbors for each node.
• Step 2: DFS Exploration:
• Start at node 0, mark it visited, explore its neighbors.
• If you hit a visited node that’s not your parent, it’s a cycle.
• Step 3: Check Connectivity:
• Ensure all nodes are visited (one component).

Step-by-Step Example

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

• Graph: 0: [1,2,3], 1: [0,4], 2: [0], 3: [0], 4: [1].
• DFS from 0:
• Visit 0, explore 1 (parent 0), 2 (parent 0), 3 (parent 0).
• From 1, explore 4 (parent 1).
• Visited: [0,1,2,3,4], no cycles.
• Result: true.

Code for DFS Approach

Copy codeclass Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Step 1: Check edge count
        if len(edges) != n - 1:
            return False

        # Step 2: Build adjacency list
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Step 3: DFS to detect cycles
        visited = set()

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

        # Step 4: Start DFS and check connectivity
        if not dfs(0, -1):
            return False
        return len(visited) == n  # All nodes must be connected

• Time Complexity: O(n + e)—visits nodes and edges.
• Space Complexity: O(n)—graph and visited set.

It’s a scenic route through the graph.

Comparing the Two Solutions

• Best Solution (Union-Find):
• Pros: O(n) time, O(n) space, fast.
• Cons: Union-Find might feel new.
• Alternative Solution (DFS):
• Pros: O(n + e) time, shows graph structure.
• Cons: O(n) space, more setup.

Union-Find wins for speed.

Additional Examples and Edge Cases

Single Node

• n = 1, edges = [] → true

Cycle

• n = 3, edges = [[0,1], [1,2], [2,0]] → false

Disconnected

• n = 4, edges = [[0,1], [2,3]] → false

Both handle these well.

Complexity Breakdown

• Union-Find:
• Time: O(n)—nearly linear.
• Space: O(n)—parent array.
• DFS:
• Time: O(n + e)—nodes + edges.
• Space: O(n)—graph and set.

Union-Find is leaner.

Key Takeaways

• Union-Find: Connects and checks cycles fast.
• DFS: Explores paths, spots loops.
• Trees: Need n-1 edges, no cycles.
• Python Tip: Lists make graphs easy—see [Python Basics](/python/basics).

Final Thoughts: Validate Trees Like a Pro

LeetCode 261: Graph Valid Tree in Python is a fantastic graph adventure. The Union-Find solution speeds through efficiently, while DFS offers a clear map. Want more? Try LeetCode 207: Course Schedule or LeetCode 323: Number of Connected Components. Ready to check? Head to Solve LeetCode 261 on LeetCode and validate that tree today!