Graph Valid Tree

Problem

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Examples

Example 1:

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

Example 2:

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

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

Solution

A tree is a special undirected graph. It satisfies two properties

1. It is connected
2. It has no cycle.

This problem can be converted to finding a cycle in a graph. It can be solved by using DFS (Recursion) or BFS (Queue).

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/1chWScEYOqc" frameborder="0" allowfullscreen></iframe></div>

Method 1 - DFS

In an undirected graph, visiting a child node often includes revisiting its parent, leading to a trivial cycle rather than a genuine one. This can be avoided by passing a parent state in the DFS call to distinguish valid backtracking. Additionally, if the number of visited nodes equals the total nodes in the graph, it ensures the graph is connected.

Approach

1. Pre-check: If the number of edges is not n-1, return false immediately because a valid tree must have exactly n-1 edges.
2. Graph Representation:
   • Use an adjacency list to represent the graph.
3. DFS/BFS for Connectivity:
   • Starting from a node, traverse the graph (using DFS or BFS).
   • Track visited nodes to ensure no cycles.
   • After traversal, check if all nodes were visited (to confirm connectivity).

Code

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Condition 0: Handle empty graph case
        if (n == 0) return true;

        // Condition 1: A tree must have exactly n-1 edges.
        if (edges.length != n - 1) {
            return false;
        }

        // Build adjacency list
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        Set<Integer> visited = new HashSet<>();

        // DFS to check for cycles and mark visited nodes
        // Start DFS from node 0, with a dummy parent -1
        if (!dfs(adj, 0, -1, visited)) {
            return false; // Cycle detected
        }

        // Condition 2: All nodes must be connected.
        // If the graph is a valid tree, all n nodes should have been visited.
        return visited.size() == n;
    }

    private boolean dfs(Map<Integer, List<Integer>> adj, int curr, int parent, Set<Integer> visited) {
        visited.add(curr);

        for (int neighbor : adj.get(curr)) {
            if (neighbor == parent) {
                continue; // Don't go back to parent
            }
            if (visited.contains(neighbor)) {
                return false; // Cycle detected: visited neighbor is not parent
            }
            if (!dfs(adj, neighbor, curr, visited)) {
                return false; // Propagate cycle detection from deeper call
            }
        }
        return true; // No cycle found from this path
    }
}

Python

from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # Condition 0: Handle empty graph case
        if n == 0: return True

        # Condition 1: A tree must have exactly n-1 edges.
        if len(edges) != n - 1:
            return False

        # Build adjacency list
        adj = {i: [] for i in range(n)}
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        visited = set()

        # DFS to check for cycles and mark visited nodes
        # Start DFS from node 0, with a dummy parent -1
        def dfs(curr, parent):
            visited.add(curr)
            for neighbor in adj[curr]:
                if neighbor == parent:
                    continue # Don't go back to parent
                if neighbor in visited:
                    return False # Cycle detected: visited neighbor is not parent
                if not dfs(neighbor, curr):
                    return False # Propagate cycle detection from deeper call
            return True # No cycle found from this path

        # If DFS from node 0 detects a cycle, or not all nodes are visited, it's not a valid tree.
        # Condition 2: All nodes must be connected and acyclic.
        return dfs(0, -1) and len(visited) == n

Complexity

• ⏰ Time complexity: O(n + e) where n is the number of nodes and e is the number of edges. This accounts for iterating through nodes and edges.
• 🧺 Space complexity: O(n + e) for the graph representation and the visited set.

Method 2 - BFS

The BFS approach ensures:

1. No Cycles: During the traversal, if we encounter a node that has already been visited (and is not the parent of the current node), then we have a cycle.
2. Connectivity: After traversal, all nodes must have been visited to confirm connectivity.

Code

Java

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        
        // Build adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // BFS traversal
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {0, -1});  // {node, parent}
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int parent = current[1];
            
            if (visited.contains(node)) {
                return false;
            }
            
            visited.add(node);
            for (int nbr : graph.get(node)) {
                if (nbr != parent) {
                    queue.add(new int[] {nbr, node});
                }
            }
        }
        
        // Ensure all nodes are connected
        return visited.size() == n;
    }
}

Python

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        # Construct adjacency list
        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = set()
        queue: Deque[(int, int)] = deque([(0, -1)])  # (node, parent)
        
        while queue:
            node, parent = queue.popleft()
            if node in visited:
                return False
            
            visited.add(node)
            for nbr in graph[node]:
                if nbr != parent:  # Avoid revisiting the parent
                    queue.append((nbr, node))
        
        # Check for connectivity
        return len(visited) == n

Complexity

• ⏰ Time complexity: O(n + e)
  • Adding edges to the graph takes O(e).
  • BFS traversal takes O(n + e) for nodes and edges.
• 🧺 Space complexity: O(n + e)
  • The adjacency list takes O(n + e).
  • The queue and visited set together take O(n).