Graph Valid Tree medium

Problem Statement

Given n nodes labeled from 0 to n - 1 and a list of edges, where edges[i] = [ui, vi] represents a directed edge from node ui to node vi, determine if the edges form a valid undirected graph that is a tree.

A valid tree is a connected acyclic undirected graph. In other words, it must satisfy the following two properties:

• Connected: There is a path between every pair of nodes.
• Acyclic: It contains no cycles.

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],[3,4],[4,0]] Output: false

Steps

1. Validate the number of edges: A tree with n nodes has exactly n-1 edges. If the number of edges doesn't match this, it's not a tree.

2. Detect Cycles using Depth First Search (DFS): We'll use DFS to traverse the graph. We'll keep track of visited nodes and nodes currently in the recursion stack. If we encounter a visited node that's also in the recursion stack, it means we've found a cycle.

3. Check Connectivity: After DFS, we need to ensure all nodes are visited. If not, the graph is not connected.

4. Build Adjacency List: Convert the edge list into an adjacency list for easier graph traversal.

Explanation

The solution uses Depth-First Search (DFS) to check for cycles and connectivity simultaneously.

• Cycle Detection: During DFS, if we encounter a node that is already visited and is currently in the recursion stack (meaning it's part of the current path), we have a cycle.

• Connectivity Check: After DFS, if the number of visited nodes is less than n, the graph is not connected.

The adjacency list representation improves the efficiency of graph traversal compared to searching through the edge list repeatedly.

Code

def validTree(n, edges):
    """
    Determines if a graph represented by edges is a valid tree.

    Args:
        n: The number of nodes in the graph.
        edges: A list of edges, where each edge is a list [u, v] representing a connection between nodes u and v.

    Returns:
        True if the graph is a valid tree, False otherwise.
    """

    # Check edge count:  A tree with n nodes has n-1 edges.
    if len(edges) != n - 1:
        return False

    # Create an adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u) # Undirected graph - add edges in both directions

    # DFS to check for cycles and connectivity
    visited = [False] * n
    recursion_stack = [False] * n

    def dfs(node):
        visited[node] = True
        recursion_stack[node] = True

        for neighbor in adj[node]:
            if not visited[neighbor]:
                if not dfs(neighbor):
                    return False  # Cycle detected
            elif recursion_stack[neighbor]:  # Cycle detected
                return False

        recursion_stack[node] = False  # Remove from recursion stack after processing
        return True


    # Start DFS from an arbitrary node (0)
    if not dfs(0):
        return False

    # Check if all nodes are visited
    return all(visited)


# Example Usage
n1 = 5
edges1 = [[0,1],[0,2],[0,3],[1,4]]
print(validTree(n1, edges1)) # Output: True

n2 = 5
edges2 = [[0,1],[1,2],[2,3],[3,4],[4,0]]
print(validTree(n2, edges2)) # Output: False

n3 = 1
edges3 = []
print(validTree(n3, edges3)) # Output: True

n4 = 4
edges4 = [[0,1],[2,3]]
print(validTree(n4, edges4)) # Output: False

Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is due to the DFS traversal.
• Space Complexity: O(V), primarily due to the visited and recursion_stack arrays, and the adjacency list. In the worst case (a complete graph), the adjacency list would take O(V^2) space, but for a tree, it remains O(V).