LeetCode Solution 261 - Graph Valid Tree

Problem Statement

Given n nodes labeled from 0 to n-1 and a list of edges where edges[i] = [ai, bi] represents an undirected edge between nodes ai and bi, write a function to determine if these edges make up a valid tree.

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 2000
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi

Optimal Approach

To determine if the given graph is a valid tree, we must check two conditions:

1. The graph should be fully connected (All nodes must be reachable from any node).
2. The graph should be acyclic (No cycles should be present).

A tree with n nodes must have exactly n-1 edges. If edges.size() != n-1, we can return false immediately.

We can solve this problem efficiently using Union-Find (Disjoint Set) or DFS/BFS traversal.

LeetCode-Compatible C++ Solution (Union-Find)

class Solution {
public:
    class UnionFind {
    private:
        vector<int> parent;
        vector<int> rank;
    public:
        UnionFind(int n) {
            parent.resize(n);
            rank.resize(n, 1);
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // Path compression
            }
            return parent[x];
        }
        bool unionSet(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return false; // Cycle detected
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
    };
    
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false; // Must have exactly n-1 edges
        UnionFind uf(n);
        for (const auto& edge : edges) {
            if (!uf.unionSet(edge[0], edge[1])) return false; // Cycle detected
        }
        return true;
    }
};

Step-by-Step Explanation of Code

1. Union-Find Data Structure
   • Each node is initially its own parent.
   • Path compression optimizes the find operation.
   • Union by rank keeps the tree balanced.
2. Checking Tree Properties
   • If the number of edges is not n-1, return false.
   • Process each edge, and if a cycle is found, return false.
   • If all edges are processed without forming a cycle, return true.

Dry Run / Execution Steps

Example Input:

n = 5
edges = {{0,1},{0,2},{0,3},{1,4}}

Execution Steps:

1. Initialize UnionFind with parent pointers [0,1,2,3,4].
2. Process 0-1 → Union → [0,0,2,3,4].
3. Process 0-2 → Union → [0,0,0,3,4].
4. Process 0-3 → Union → [0,0,0,0,4].
5. Process 1-4 → Union → [0,0,0,0,0].
6. No cycles detected, and all nodes are connected → Valid Tree.

Alternative Approaches

1. DFS/BFS Traversal

• Start from node 0, traverse all nodes using DFS or BFS.
• Maintain a visited set and detect cycles.
• If all nodes are visited exactly once and no cycle exists, return true.

DFS Solution (C++)

class Solution {
public:
    bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
        visited[node] = true;
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                if (!dfs(neighbor, node, adj, visited)) return false;
            } else if (neighbor != parent) {
                return false; // Cycle detected
            }
        }
        return true;
    }
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(n, false);
        if (!dfs(0, -1, adj, visited)) return false;
        for (bool v : visited) {
            if (!v) return false;
        }
        return true;
    }
};

Why Union-Find is Preferred?

Approach	Time Complexity	Space Complexity	Best for Large Graphs?
Union-Find	O(N)	O(N)	✅ Yes
DFS/BFS	O(N)	O(N)	❌ No (Stack/Queue Overhead)

Union-Find is optimal because it avoids recursive function calls and provides near-constant time operations with path compression.

Conclusion

The best approach to solve this problem efficiently is Union-Find (Disjoint Set Union - DSU) because it allows quick cycle detection and connectivity check in O(N) time. Alternative approaches like DFS/BFS work but introduce recursion/queue overhead.

Similar Problems for Practice

• Number of Connected Components in an Undirected Graph (LeetCode 323)
• Redundant Connection (LeetCode 684)
• Course Schedule (LeetCode 207)