Graph Valid Tree

Problem

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

Constraints:

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no self-loops or repeated edges.

Solution

Approach 1: Union-Find

The key insight is that a valid tree must satisfy two conditions:

Exactly n-1 edges (tree property)
No cycles (all nodes in one connected component)

Implementation

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Tree with n nodes must have exactly n-1 edges
        if len(edges) != n - 1:
            return False

        parent = list(range(n))

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

        def union(x, y):
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return False  # Cycle detected

            parent[root_x] = root_y
            return True

        # Process all edges
        for u, v in edges:
            if not union(u, v):
                return False  # Cycle found

        return True

Approach 2: DFS with Cycle Detection

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

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

        visited = set()

        def dfs(node, parent):
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                if neighbor in visited:
                    return False  # Cycle detected
                if not dfs(neighbor, node):
                    return False

            return True

        # Check for cycles and ensure all nodes are visited (connected)
        return dfs(0, -1) and len(visited) == n

Approach 3: BFS with Cycle Detection

from collections import deque

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

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

        visited = set([0])
        queue = deque([(0, -1)])  # (node, parent)

        while queue:
            node, parent = queue.popleft()

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                if neighbor in visited:
                    return False  # Cycle detected

                visited.add(neighbor)
                queue.append((neighbor, node))

        return len(visited) == n

Complexity Analysis

Union-Find Approach:

Time Complexity: O(E * α(n)), where E is number of edges and α is inverse Ackermann function.
Space Complexity: O(n) for parent array.

DFS/BFS Approaches:

Time Complexity: O(n + E), visiting all nodes and edges.
Space Complexity: O(n + E) for adjacency list and visited set.

Key Insights

Tree Properties: A valid tree with n nodes must have:
- Exactly n-1 edges
- No cycles
- All nodes connected (one component)
Edge Count Check: Quick initial check - if edges ≠ n-1, cannot be a tree.
Cycle Detection: Union-Find detects cycles when trying to connect already-connected nodes.
Connectivity Check: DFS/BFS approaches verify all nodes are reachable from one starting node.
Parent Tracking: In DFS/BFS for undirected graphs, we track parent to avoid false cycle detection from the edge we came from.
Union-Find Simplicity: With correct edge count, Union-Find just needs to check for cycles - connectivity is guaranteed.