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.

python
# Pseudo-code for Naive Approach
def validTree(n, edges):
    # 1. Build Adjacency Matrix (Space O(N^2))
    adj = [[0] * n for _ in range(n)]
    for u, v in edges:
        adj[u][v] = adj[v][u] = 1

    # 2. Check Connectivity (Time O(N * (N + E)))
    # Run BFS/DFS from every node to every other node
    for i in range(n):
        for j in range(i + 1, n):
            if not hasPath(i, j, adj):
                return False
    
    # 3. Check Cycles
    # ... additional traversal logic ...
    
    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$).

Core Insight for Graph Valid Tree

The core insight for solving LeetCode 261 efficiently lies in the definition of a tree in graph theory. A graph with $n$ nodes is a tree if and only if:

1. It has exactly $n - 1$ edges.
2. It contains no cycles.

If a graph has $n - 1$ edges and no cycles, it is guaranteed to be connected.

The Union-Find data structure is optimized for two specific operations: find (determining which subset a generic element belongs to) and union (joining two subsets into a single subset).

By processing the edges one by one using Union-Find, we can enforce the tree constraints:

1. Cycle Detection: Before adding an edge between node u and node v, we check if they essentially belong to the same set (i.e., find(u) == find(v)). If they do, a path already exists between them, and adding this edge would close a loop, creating a cycle.
2. Connectivity: We start with $n$ disjoint sets (each node is its own parent). Every successful union operation reduces the number of disjoint sets by one. For a valid tree, after processing all edges, we must have exactly 1 connected component remaining.

Visual Description: Imagine the algorithm state as a collection of disjoint sets. Initially, every node is an isolated root [0, 1, 2, ...]. When an edge [0, 1] is processed, the set containing 0 merges with the set containing 1. The structure updates to point 1 towards 0. If we later encounter an edge connecting two nodes that already trace back to the same root (e.g., 0), the algorithm immediately identifies a cycle.

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.

Reference Implementation

C++ Solution for LeetCode 261

cpp
class Solution {
public:
    // Helper function to find the representative of the set
    int find(int node, vector<int>& parent) {
        if (parent[node] == node) {
            return node;
        }
        // Path compression: point node directly to root
        return parent[node] = find(parent[node], parent);
    }

    bool validTree(int n, vector<vector<int>>& edges) {
        // Condition 1: A tree with n nodes must have exactly n-1 edges
        if (edges.size() != n - 1) {
            return false;
        }

        // Initialize DSU structure
        vector<int> parent(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }

        // Process edges
        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];

            int rootU = find(u, parent);
            int rootV = find(v, parent);

            // Condition 2: If roots are same, a cycle exists
            if (rootU == rootV) {
                return false;
            }

            // Union the sets
            parent[rootU] = rootV;
        }

        // If we processed n-1 edges without cycles, it is a valid tree
        return true;
    }
};

Java Solution for LeetCode 261

java
class Solution {
    // Helper method to find the representative with path compression
    private int find(int node, int[] parent) {
        if (parent[node] == node) {
            return node;
        }
        parent[node] = find(parent[node], parent); // Path compression
        return parent[node];
    }

    public boolean validTree(int n, int[][] edges) {
        // A valid tree with n nodes must have exactly n-1 edges
        if (edges.length != n - 1) {
            return false;
        }

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            int rootU = find(u, parent);
            int rootV = find(v, parent);

            // If they share the same root, a cycle is detected
            if (rootU == rootV) {
                return false;
            }

            // Union logic
            parent[rootU] = rootV;
        }

        return true;
    }
}

Python Solution for LeetCode 261

python
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A tree must have exactly n - 1 edges
        if len(edges) != n - 1:
            return False
        
        parent = list(range(n))
        
        def find(node):
            if parent[node] != node:
                # Path compression
                parent[node] = find(parent[node])
            return parent[node]
        
        for u, v in edges:
            root_u = find(u)
            root_v = find(v)
            
            # If roots are the same, a cycle exists
            if root_u == root_v:
                return False
            
            # Union the sets
            parent[root_u] = root_v
            
        return True