Graph Valid Tree

Problem Statement

You’re a graph botanist verifying if an undirected graph with n nodes and edges forms a tree—no cycles, fully connected. Return true if it’s a valid tree. This medium-level DFS/Union-Find challenge is a structural study—prune those loops!

Example

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Graph:

  0
 /|\
1 2 3
|
4

Output: true (Tree: n-1 edges, no cycle)

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

Output: false (Cycle: 1-2-3-1)

Code

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List> 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]);
        }
        boolean[] visited = new boolean[n];
        dfs(graph, 0, -1, visited);
        for (boolean v : visited) if (!v) return false; // Check connectivity
        return true;
    }
    private boolean dfs(List> graph, int node, int parent, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                if (!dfs(graph, neighbor, node, visited)) return false;
            } else if (neighbor != parent) {
                return false; // Cycle
            }
        }
        return true;
    }
}
            

from collections import defaultdict
def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * n
    def dfs(node, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor, node)
            elif neighbor != parent:
                return False
        return True
    dfs(0, -1)
    return all(visited)  # Ensure fully connected
            

function validTree(n, edges) {
    if (edges.length !== n - 1) return false;
    let graph = Array(n).fill().map(() => []);
    for (let [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    let visited = new Array(n).fill(false);
    function dfs(node, parent) {
        visited[node] = true;
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, node);
            } else if (neighbor !== parent) {
                return false;
            }
        }
        return true;
    }
    dfs(0, -1);
    return visited.every(v => v);
}
            

Explanation

• Tree Insight: n-1 edges + no cycles + connected = tree.
• Flow: Check edge count, DFS for cycles, verify all nodes visited.
• Example Walkthrough: [0,1],[1,2],[2,0] → n-1 fails, cycle detected → false.
• Union-Find Alt: Merge edges, check for cycles and single component.
• Key Check: Edge count shortcut eliminates non-trees early.

Note