Graph Valid Tree medium

Problem Statement

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (represented as a 2D integer array edges), write a function to check if these edges form a valid tree.

A valid tree is a connected acyclic graph. In other words, a valid tree has exactly n - 1 edges and there are no cycles.

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true Explanation: The given edges form a valid tree.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]] Output: false Explanation: This graph has a cycle.

Steps

1. Edge Count Check: First, check if the number of edges is equal to n - 1. If not, it cannot be a valid tree.

2. Cycle Detection using Depth-First Search (DFS): We'll use DFS to detect cycles. We'll keep track of visited nodes and nodes currently in the recursion stack (to detect cycles).

3. Connectedness Check: After the DFS, verify that all nodes have been visited. If not, the graph is not connected.

Explanation

The algorithm leverages Depth-First Search (DFS) to efficiently check for cycles and connectivity. A valid tree is both connected (you can reach every node from any other node) and acyclic (contains no cycles).

The DFS traversal marks nodes as visited and keeps track of the nodes currently being visited (recursion stack). If we encounter a visited node that is also in the recursion stack, it means we've found a cycle. After the DFS, if the number of visited nodes is less than n, then the graph is not connected.

Code

function validTree(n: number, edges: number[][]): boolean {
    // Edge count check
    if (edges.length !== n - 1) return false;

    // Adjacency list representation of the graph
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u); // Undirected graph
    }

    const visited: boolean[] = Array(n).fill(false);
    const recursionStack: boolean[] = Array(n).fill(false);

    const dfs = (node: number): boolean => {
        visited[node] = true;
        recursionStack[node] = true;

        for (const neighbor of graph[node]) {
            if (!visited[neighbor]) {
                if (!dfs(neighbor)) return false;
            } else if (recursionStack[neighbor]) {
                return false; // Cycle detected
            }
        }

        recursionStack[node] = false; // Remove from recursion stack after processing
        return true;
    };


    // Start DFS from node 0 (you can start from any node)
    if (!dfs(0)) return false;

    // Check connectivity:  All nodes should be visited
    for (let i = 0; i < n; i++) {
        if (!visited[i]) return false;
    }

    return true;
};

Complexity

• Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. This is because the DFS visits each node and edge once.
• Space Complexity: O(N), primarily due to the visited and recursionStack arrays, and the adjacency list graph. The recursion stack space during DFS also contributes to this.