Graph Valid Tree medium

Problem Statement

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

A valid tree is a graph where:

1. There are n nodes in the graph.
2. The graph is connected.
3. There are n - 1 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],[3,4],[4,0],[4,1]] Output: false

Steps to Solve

1. Check Number of Edges: If the number of edges is not n - 1, it cannot be a tree.
2. Detect Cycles: Use Depth-First Search (DFS) or Breadth-First Search (BFS) to detect cycles. A cycle indicates that the graph is not a tree.
3. Check Connectivity: Ensure that all nodes are reachable from a single starting node. If not all nodes are visited after a DFS or BFS traversal starting from a single node, the graph is not connected.

Explanation

The solution employs Depth-First Search (DFS) to check for cycles and connectivity simultaneously. We maintain a visited array to track visited nodes and a recursionStack to track nodes currently in the recursion call stack (essential for cycle detection).

• If an edge leads to a node already in recursionStack, a cycle exists.
• If DFS completes and the count of visited nodes is not equal to n, the graph is not connected.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public bool ValidTree(int n, int[][] edges) {
        if (edges.Length != n - 1) return false; // Check edge count

        // Adjacency list representation of the graph
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new List<int>();
        }
        foreach (int[] edge in edges) {
            adjList[edge[0]].Add(edge[1]);
            adjList[edge[1]].Add(edge[0]); // Assuming undirected graph
        }

        bool[] visited = new bool[n];
        bool[] recursionStack = new bool[n];
        
        if (dfs(adjList, 0, visited, recursionStack)) return false; //cycle detected

        for(int i=0; i<n; i++){
            if(!visited[i]) return false; // Not connected
        }
        return true;
    }

    private bool dfs(List<int>[] adjList, int u, bool[] visited, bool[] recursionStack) {
        visited[u] = true;
        recursionStack[u] = true;

        foreach (int v in adjList[u]) {
            if (!visited[v]) {
                if (dfs(adjList, v, visited, recursionStack)) return true;
            } else if (recursionStack[v]) {
                return true; // Cycle detected
            }
        }
        recursionStack[u] = false;
        return false;
    }
}

Complexity

• Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. This is because of the DFS traversal.
• Space Complexity: O(N) due to the visited and recursionStack arrays, and the adjacency list. The recursion stack used by DFS also contributes to this space complexity.