Code Implementation

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

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

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

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

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

        return True
      

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        vector<int> parent(n);
        for (int i = 0; i < n; ++i) parent[i] = i;

        function<int(int)> find = [&](int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            int pu = find(u), pv = find(v);
            if (pu == pv) return false;
            parent[pv] = pu;
        }
        return true;
    }
};
      

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;

        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            int pu = find(u), pv = find(v);
            if (pu == pv) return false;
            parent[pv] = pu;
        }
        return true;
    }
}
      

var validTree = function(n, edges) {
    if (edges.length !== n - 1) return false;
    let parent = Array(n).fill(0).map((_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    for (let [u, v] of edges) {
        let pu = find(u), pv = find(v);
        if (pu === pv) return false;
        parent[pv] = pu;
    }
    return true;
};
      

Problem Description

You are given two inputs: an integer n representing the number of nodes labeled from 0 to n - 1, and a list of undirected edges edges where each edge connects two nodes. Your task is to determine if these edges form a valid tree.

• A valid tree is an undirected graph that is both connected (every node is reachable from every other node) and acyclic (no cycles).
• You must use each edge at most once and cannot reuse elements.
• There is only one unique solution for the given input.

For example, given n = 5 and edges = [[0,1],[0,2],[0,3],[1,4]], the function should return true because the edges form a valid tree.

Thought Process

The problem asks whether the given edges form a valid tree. Let's recall the properties of a tree:

• It is connected: there is a path between every pair of nodes.
• It is acyclic: there are no cycles.
• For n nodes, a tree has exactly n - 1 edges.

The brute-force way would be to check for cycles and ensure all nodes are connected, perhaps using DFS or BFS for each node. But this can be inefficient for large graphs.

An optimized approach is to use the Union-Find (Disjoint Set Union) data structure, which efficiently detects cycles and helps us determine if the graph is connected as we process each edge.

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Check the number of edges.
   • If the number of edges is not exactly n - 1, it's impossible to form a tree (either there are too many edges, creating a cycle, or too few, making the graph disconnected).
2. Initialize Union-Find structure.
   • Create a parent array where each node is its own parent initially.
3. Process each edge.
   • For each edge [u, v], try to union their sets.
   • If u and v already have the same root, a cycle is detected, so return false.
   • Otherwise, union them by setting one's root as the parent of the other.
4. Return true if all edges processed without finding a cycle.
   • Since the edge count is n-1, and no cycles were found, the graph is connected and acyclic, hence a tree.

We use Union-Find because it allows us to efficiently check if two nodes are already connected (detecting cycles) and to merge their sets (ensuring connectivity), both in nearly constant time.

Example Walkthrough

Let's walk through an example with n = 5 and edges = [[0,1],[0,2],[0,3],[1,4]]:

1. Number of edges = 4, which is n-1 (good).
2. Initialize parent = [0, 1, 2, 3, 4].
3. Process edge [0,1]:
   • Find root of 0: 0; root of 1: 1.
   • Different roots, union them: parent[1] = 0.
4. Process edge [0,2]:
   • Find root of 0: 0; root of 2: 2.
   • Union: parent[2] = 0.
5. Process edge [0,3]:
   • Find root of 0: 0; root of 3: 3.
   • Union: parent[3] = 0.
6. Process edge [1,4]:
   • Find root of 1: parent[1]=0, so root is 0; root of 4: 4.
   • Union: parent[4] = 0.
7. All edges processed, no cycles found. All nodes are connected under root 0, so it's a valid tree.

Time and Space Complexity

Brute-force approach:

• Using DFS/BFS to check connectivity and cycles: O(N + E) time, but may require extra passes and visited sets.
• Space: O(N) for visited nodes and recursion/queue.

• Each find and union operation is nearly O(1) due to path compression.
• We process each edge once: O(E * α(N)), where α(N) is the inverse Ackermann function (very slow-growing, almost constant for practical N).
• Space: O(N) for the parent array.

In practice, the Union-Find approach is very efficient for this problem.

Summary

To determine if a set of edges forms a valid tree, we check that the number of edges is exactly n-1 and use the Union-Find algorithm to ensure there are no cycles and all nodes are connected. This approach is both intuitive and highly efficient, leveraging the mathematical properties of trees and the power of the Union-Find data structure. The solution is elegant because it reduces a seemingly complex graph problem to a few simple, fast checks.