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:

1
2

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

Example 2:

1
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).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        # Constructing adjacency list
        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = set()
        
        def dfs(node: int, parent: int) -> bool:
            if node in visited:
                return False
            visited.add(node)
            for nbr in graph[node]:
                if nbr != parent:
                    if not dfs(nbr, node):
                        return False
            return True
        
        # Check for cycles
        if not dfs(0, -1):
            return False
        
        # Check for connectivity
        return len(visited) == n
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Pre-check for edge count
        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]);
        }
        
        // Set to track visited nodes
        Set<Integer> visited = new HashSet<>();
        
        // DFS function
        if (!dfs(0, -1, graph, visited)) {
            return false;
        }
        
        // Check connectivity
        return visited.size() == n;
    }
    
    private boolean dfs(int node, int parent, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        if (visited.contains(node)) {
            return false;
        }
        visited.add(node);
        for (int nbr : graph.get(node)) {
            if (nbr != parent) {
                if (!dfs(nbr, node, graph, visited)) {
                    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 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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).