Problem Statement

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.

A valid tree is a graph that meets two specific conditions:

1. It is fully connected (all nodes can be reached from a single starting point).
2. It contains absolutely no cycles.

Additional information

• 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.

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

Explanation: The graph contains a cycle connecting nodes 1, 2, and 3.

Depth-First Search (DFS)

Intuition

To be a valid tree, an undirected graph of n nodes must pass a strict mathematical test before we even look at the connections: it must have exactly n - 1 edges.

• If it has fewer than n - 1 edges, it is impossible for all nodes to be connected.
• If it has more than n - 1 edges, it is mathematically guaranteed to contain a cycle.

If the edge count is exactly n - 1, our only remaining job is to prove the graph is fully connected. We can do this by running a standard Depth-First Search (DFS) starting from node 0. If the DFS manages to visit every single node in the graph, we have a perfectly connected valid tree!

Algorithm

1. Mathematical Pruning: Check if len(edges) != n - 1. If true, return False immediately.
2. Initialize an empty adjacency list adj using a dictionary.
3. Iterate through edges and populate the adjacency list in both directions (since the graph is undirected).
4. Initialize a visited set to track processed nodes.
5. Define a recursive helper function dfs(node):

• Add node to visited.
• Loop through all neighbors of node in adj.
• If a neighbor is not in visited, recursively call dfs(neighbor).

6. Call dfs(0) to start exploring from the first node.
7. Check if the length of the visited set is equal to n. If it is, all nodes are connected. Return True. Otherwise, return False.

def valid_tree(n: int, edges: list[list[int]]) -> bool:
    # A valid tree must have exactly n - 1 edges
    if len(edges) != n - 1:
        return False
        
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        
    visited = set()
    
    def dfs(node):
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                dfs(neighbor)
                
    # Start DFS from node 0
    dfs(0)
    
    # If we visited all nodes, it's a fully connected valid tree
    return len(visited) == n

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: We iterate through all Edges (E) to build the adjacency list. During the DFS, we visit every Vertex (V) exactly once. Because we enforce E == V - 1 at the very start, the time complexity simplifies to strictly O(N).

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space. The visited set and the recursion stack take up to O(V) space. Simplified, this is O(N) space.

Union-Find (Disjoint Set) - Optimal Space

Intuition

We can completely avoid building an adjacency list or running a deep recursion stack by using the Union-Find algorithm.

Just like the DFS approach, we first check if there are exactly n - 1 edges. If there are, we iterate through the edges and connect (Union) the nodes. If we attempt to Union two nodes that already share the same "root" parent, we have just found a redundant connection that creates a cycle! If we process every edge without hitting any cycles, the graph is a valid tree.

Algorithm

1. Mathematical Pruning: If len(edges) != n - 1, return False.
2. Initialize a parent array of size n where parent[i] = i.
3. Define the find(node) function with Path Compression:

• Traverse up the parent pointers until p == parent[p].
• Compress the path by pointing nodes directly to their grandparent.

4. Define the union(n1, n2) function:

• Find the roots p1 and p2.
• If p1 == p2, they are already connected. A cycle exists! Return False.
• Otherwise, attach p1 to p2. Return True.

5. Iterate through each u, v in edges.
6. If union(u, v) returns False, return False.
7. If all edges are processed successfully, return True.

def valid_tree(n: int, edges: list[list[int]]) -> bool:
    # A valid tree must have exactly n - 1 edges
    if len(edges) != n - 1:
        return False
        
    parent = [i for i in range(n)]
    
    def find(node):
        p = parent[node]
        while p != parent[p]:
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p
        
    def union(n1, n2):
        p1, p2 = find(n1), find(n2)
        
        # Cycle detected
        if p1 == p2:
            return False
            
        parent[p1] = p2
        return True
        
    for u, v in edges:
        if not union(u, v):
            return False
            
    return True

Time & Space Complexity

• Time complexity: O(N)

• Reason: Checking n - 1 edges instantly enforces that we process at most O(N) edges. The Union-Find operations take amortized O(1) time due to Path Compression.

• Space complexity: O(N)

• Reason: We completely avoid building an adjacency list. The parent array takes exactly O(N) space.