Domain 2MediumCORE

Graph Valid Tree

We are given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges. We need to determine if this specific structure forms a valid tree.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search#Union Find#Graph

261. Graph Valid Tree

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Union Find,Graph
FAANG asked: 1
Acceptance rate: 43.3%


Problem Breakdown

We are given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges. We need to determine if this specific structure forms a valid tree.

A valid tree must satisfy two strict conditions:

  1. Connectivity: All n nodes must be reachable from any other node (single connected component).
  2. Acyclicity: There must be no cycles in the graph.

Implicit constraints and edge cases to consider:

  • If there are no edges (edges list empty), it’s only a tree if n=1n=1. For n>1n > 1, an empty edge set implies disconnected components, so return False.
  • A graph with n-1 edges is necessary but not sufficient (could be disconnected). We must verify connectivity explicitly or rely on the property that for undirected graphs: Connected + Acyclic   ⟺  \iff Edges = n - 1. Note: The constraint text provided in the prompt (1 <= 2000 <= n) contains a typo. Based on standard LeetCode constraints and problem logic, we assume 1≤n1 \le n.

Intuition

A brute-force approach would involve running a traversal (DFS/BFS) from an arbitrary node to count reachable nodes. If we visit all n nodes, it’s connected. However, checking for cycles during this traversal requires tracking the parent pointer or using a visited set carefully to distinguish between back-edges and tree edges.

The key insight is that Union-Find (Disjoint Set Union - DSU) handles both conditions elegantly:

  1. Cycle Detection: When processing an edge (u, v), if find(u) equals find(v), they are already connected; adding this edge creates a cycle. We return False immediately.
  2. Connectivity Check: A tree with n nodes must have exactly n-1 edges and no cycles. If we process all edges without finding a cycle, the graph is acyclic. To ensure it’s also connected (and not just a forest), we can verify that after processing all valid unions, there is only one remaining component or simply check if the number of successful union operations equals n-1.

Union-Find offers nearly constant time complexity per operation (O(α(n))O(\alpha(n))) and avoids recursion depth issues associated with deep DFS trees in Python.

Approach

We will use a Union-Find data structure to manage connected components.

  1. Initialization: Create a parent array where each node is its own parent initially (parent[i] = i). We can optionally track rank/size for optimization, but path compression alone suffices here given the constraints.
  2. Edge Count Check: Before processing edges, verify len(edges) == n - 1. If not, it cannot be a tree (either disconnected or contains cycles). Return False immediately if this check fails. This handles all cases where nodes are isolated or form a forest rather than one component efficiently.
  3. Edge Processing: Iterate through every edge [u, v].
    • Find the root of u and v.
    • If roots are identical (find(u) == find(v)), a cycle exists. Return False immediately.
    • Otherwise, union the two sets (make one parent point to another). We do not need a separate counter if we rely on the edge count check upfront; finding no cycles with exactly n-1 edges guarantees connectivity.
  4. Return: If no cycle was detected AND the graph structure matches tree properties (checked via edge count), return True.

Complexity Analysis

  • Time Complexity: O(E⋅α(N))O(E \cdot \alpha(N)), where EE is number of edges and α\alpha is the inverse Ackermann function (effectively constant). In practice, this behaves as linear time relative to input size. We iterate through each edge once. The path compression ensures amortized nearly-constant time per operation.
  • Space Complexity: O(N)O(N) for storing the parent array in Union-Find structure.

Solution

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A tree with N nodes must have exactly N-1 edges to be connected and acyclic.
        if len(edges) != n - 1:
            return False
        
        parent = list(range(n))
        
        def find(i):
            root = i
            while parent[root] != root:
                root = parent[root]
            
            # Path compression step to flatten structure for future lookups
            curr = i
            while curr != root:
                next_node = parent[curr]
                parent[curr] = root
                curr = next_node
            
            return root
        
        for u, v in edges:
            root_u = find(u)
            root_v = find(v)
            
            if root_u == root_v:
                # Cycle detected (already connected), so not a valid tree.
                return False
            
            # Union the sets by attaching one root to another
            parent[root_u] = root_v
        
        return True