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 tree. A valid tree is a connected, acyclic graph. In other words, it is a connected graph with n nodes and 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]] Output: false

Explanation: This forms a cycle, so it's not a valid tree.

Steps

1. Validate Number of Edges: A valid tree with n nodes has 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) or Breadth-First Search (BFS)): We'll use DFS to traverse the graph. We need to keep track of visited nodes and nodes currently in the recursion stack (to detect cycles). If we encounter a node that's already been visited and is in the recursion stack, it indicates a cycle.

3. Check Connectivity: After DFS, we check if all nodes have been visited. If not, the graph is not connected.

Explanation

The solution uses Depth-First Search (DFS) to check for cycles and connectivity simultaneously. The dfs function recursively explores the graph.

• visited: A boolean array to keep track of visited nodes.
• recursionStack: A boolean array to keep track of nodes currently in the recursion stack (during the DFS call). This is crucial for cycle detection.
• graph: An adjacency list representation of the graph for efficient neighbor lookup.

The isValidTree function first checks the number of edges. Then, it performs DFS starting from node 0. If a cycle is detected or not all nodes are visited after DFS, it returns false. Otherwise, it returns true.

Code

import java.util.*;

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

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]); // Undirected graph
        }

        boolean[] visited = new boolean[n];
        boolean[] recursionStack = new boolean[n];

        if (hasCycle(graph, 0, visited, recursionStack)) return false;

        for (boolean b : visited) {
            if (!b) return false; // Check connectivity
        }

        return true;
    }

    private boolean hasCycle(List<List<Integer>> graph, int node, boolean[] visited, boolean[] recursionStack) {
        visited[node] = true;
        recursionStack[node] = true;

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                if (hasCycle(graph, neighbor, visited, recursionStack)) return true;
            } else if (recursionStack[neighbor]) {
                return true; // Cycle detected
            }
        }

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

Complexity

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