Graph Valid Tree

LeetCode 261: Graph Valid Tree Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses the Union-Find (DSU) data structure to detect cycles and verify that the graph contains exactly one connected component with $N-1$ edges.

You are given an integer n (the number of nodes) and a list of edges. The goal is to determine if these edges form a valid tree. In the context of graph theory, a valid tree must satisfy two strict conditions: it must be fully connected (all nodes can reach each other) and it must be acyclic (contain no loops). This is a popular interview question for testing graph theory fundamentals and efficient state management.

Brute Force Approach for Graph Valid Tree

A naive brute force approach to solve the Graph Valid Tree problem focuses on verifying the two tree properties—connectivity and acyclicity—independently and inefficiently.

1. Construct the Graph: Build an adjacency matrix to represent connections between nodes.
2. Check Connectivity: To ensure the graph is connected, iterate through every pair of nodes $(u, v)$ and perform a Breadth-First Search (BFS) starting from $u$ to see if $v$ is reachable.
3. Check Cycles: Run a traversal from every node, keeping track of visited nodes in the current path. If a node is revisited, a cycle exists.

1# Pseudo-code for Naive Approach
2def validTree(n, edges):
3    # 1. Build Adjacency Matrix (Space O(N^2))
4    adj = [[0] * n for _ in range(n)]
5    for u, v in edges:
6        adj[u][v] = adj[v][u] = 1
7
8    # 2. Check Connectivity (Time O(N * (N + E)))
9    # Run BFS/DFS from every node to every other node
10    for i in range(n):
11        for j in range(i + 1, n):
12            if not hasPath(i, j, adj):
13                return False
14    
15    # 3. Check Cycles
16    # ... additional traversal logic ...
17    
18    return True

Time Complexity: $O(N \cdot (N + E))$. We potentially traverse the entire graph for every node pair verification. Why it fails: This approach results in a Time Limit Exceeded (TLE) error on large inputs. Furthermore, using an adjacency matrix requires $O(N^2)$ space, which causes Memory Limit Exceeded errors when $N$ is large (e.g., $N=2000$).

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

Although the overarching pattern is graph traversal, we utilize the Union-Find (DSU) subpattern to solve this without explicit recursion or queues.

1. Edge Count Check: First, verify if edges.length == n - 1. If the number of edges is not exactly $n - 1$, the graph cannot be a tree (either disconnected or contains cycles). Return false immediately.
2. Initialize DSU: Create a parent array of size n where parent[i] = i. This indicates that initially, each node is its own connected component.
3. Process Edges: Iterate through the edges list. For each edge [u, v]:
   • Find the root representative of u (let's call it root_u).
   • Find the root representative of v (let's call it root_v).
   • Constraint Check: If root_u == root_v, the nodes u and v are already connected via some other path. Adding this edge creates a cycle. Return false.
   • Union: If roots are different, merge the sets by setting parent[root_u] = root_v.
4. Final Result: If the loop completes without detecting a cycle, and we passed the initial edge count check, the graph is a valid tree. Return true.

Execution Flow

Let's trace the algorithm with n = 5 and edges = [[0,1], [0,2], [0,3], [1,4]].

1. Initialization:

   • parent array: [0, 1, 2, 3, 4]
   • Edge count check: 4 edges for 5 nodes. $5 - 1 = 4$. Condition passes.

2. Process Edge [0, 1]:

   • find(0) returns 0. find(1) returns 1.
   • Roots are different. Union sets.
   • parent becomes [1, 1, 2, 3, 4] (0 points to 1).

3. Process Edge [0, 2]:

   • find(0) -> points to 1. Root is 1.
   • find(2) -> returns 2. Root is 2.
   • Roots 1 and 2 are different. Union sets.
   • parent becomes [1, 1, 1, 3, 4] (2 points to 1).

4. Process Edge [0, 3]:

   • find(0) -> points to 1. Root is 1.
   • find(3) -> returns 3. Root is 3.
   • Roots 1 and 3 are different. Union sets.
   • parent becomes [1, 1, 1, 1, 4] (3 points to 1).

5. Process Edge [1, 4]:

   • find(1) -> returns 1. Root is 1.
   • find(4) -> returns 4. Root is 4.
   • Roots 1 and 4 are different. Union sets.
   • parent becomes [1, 1, 1, 1, 1] (4 points to 1).

6. Completion:

   • All edges processed. No cycles found.
   • Return true.

Proof of Correctness

The correctness relies on the properties of trees and the invariants of the Union-Find data structure.

1. Acyclic Property: The find(u) == find(v) check ensures that we never add an edge between two nodes that are already in the same connected component. This guarantees the graph remains acyclic.
2. Connected Property: A graph with $N$ nodes and no cycles is a tree if and only if it has exactly $N-1$ edges. By enforcing edges.length == n - 1 initially and ensuring no cycles exist during processing, we implicitly guarantee that the graph is fully connected. If there were no cycles but the graph was disconnected, it would require fewer than $N-1$ edges.

Pattern Reuse Notes

The Graph - Union-Find pattern used in LeetCode 261 is a fundamental technique applicable to several other problems:

• LeetCode 200: Number of Islands: While typically DFS/BFS, DSU can be used to group land cells.
• LeetCode 305: Number of Islands II: DSU is the optimal solution here to handle dynamic updates (adding land) efficiently.
• LeetCode 323: Number of Connected Components in an Undirected Graph: This is nearly identical to Graph Valid Tree; you simply count the remaining sets.
• LeetCode 547: Number of Provinces: Directly maps to finding connected components using DSU or DFS.

Reference Implementation

C++ Solution for LeetCode 261

1class Solution {
2public:
3    // Helper function to find the representative of the set
4    int find(int node, vector<int>& parent) {
5        if (parent[node] == node) {
6            return node;
7        }
8        // Path compression: point node directly to root
9        return parent[node] = find(parent[node], parent);
10    }
11
12    bool validTree(int n, vector<vector<int>>& edges) {
13        // Condition 1: A tree with n nodes must have exactly n-1 edges
14        if (edges.size() != n - 1) {
15            return false;
16        }
17
18        // Initialize DSU structure
19        vector<int> parent(n);
20        for (int i = 0; i < n; ++i) {
21            parent[i] = i;
22        }
23
24        // Process edges
25        for (const auto& edge : edges) {
26            int u = edge[0];
27            int v = edge[1];
28
29            int rootU = find(u, parent);
30            int rootV = find(v, parent);
31
32            // Condition 2: If roots are same, a cycle exists
33            if (rootU == rootV) {
34                return false;
35            }
36
37            // Union the sets
38            parent[rootU] = rootV;
39        }
40
41        // If we processed n-1 edges without cycles, it is a valid tree
42        return true;
43    }
44};

Java Solution for LeetCode 261

1class Solution {
2    // Helper method to find the representative with path compression
3    private int find(int node, int[] parent) {
4        if (parent[node] == node) {
5            return node;
6        }
7        parent[node] = find(parent[node], parent); // Path compression
8        return parent[node];
9    }
10
11    public boolean validTree(int n, int[][] edges) {
12        // A valid tree with n nodes must have exactly n-1 edges
13        if (edges.length != n - 1) {
14            return false;
15        }
16
17        int[] parent = new int[n];
18        for (int i = 0; i < n; i++) {
19            parent[i] = i;
20        }
21
22        for (int[] edge : edges) {
23            int u = edge[0];
24            int v = edge[1];
25
26            int rootU = find(u, parent);
27            int rootV = find(v, parent);
28
29            // If they share the same root, a cycle is detected
30            if (rootU == rootV) {
31                return false;
32            }
33
34            // Union logic
35            parent[rootU] = rootV;
36        }
37
38        return true;
39    }
40}

Python Solution for LeetCode 261

1class Solution:
2    def validTree(self, n: int, edges: List[List[int]]) -> bool:
3        # A tree must have exactly n - 1 edges
4        if len(edges) != n - 1:
5            return False
6        
7        parent = list(range(n))
8        
9        def find(node):
10            if parent[node] != node:
11                # Path compression
12                parent[node] = find(parent[node])
13            return parent[node]
14        
15        for u, v in edges:
16            root_u = find(u)
17            root_v = find(v)
18            
19            # If roots are the same, a cycle exists
20            if root_u == root_v:
21                return False
22            
23            # Union the sets
24            parent[root_u] = root_v
25            
26        return True