Sponsored
Sponsored
Performing Depth-First Search (DFS) is a common way to traverse a tree or graph. We'll start from node 0 and explore as far as possible along each branch before backtracking, avoiding restricted nodes and those already visited.
Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.
1from collections import defaultdict
2
3def reachableNodes(n, edges, restricted):
4 adj_list = defaultdict(list)
5 restricted_set = set(restricted)
6 for a, b in edges:
7 adj_list[a].append(b)
8 adj_list[b].append(a)
9
10 def dfs(node, visited):
11 if node in visited or node in restricted_set:
12 return 0
13 visited.add(node)
14 count = 1
15 for neighbor in adj_list[node]:
16 count += dfs(neighbor, visited)
17 return count
18
19 return dfs(0, set())The Python solution uses defaultdict for adjacency list storage, and a set to keep track of visited nodes. DFS traverses from node 0 while avoiding restricted nodes.
Breadth-First Search (BFS) can also be used to traverse the tree level-by-level. Starting from node 0, visit all neighbors at the current depth before moving on to nodes at the next depth level, while skipping restricted nodes.
Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.
1
This BFS approach uses an adjacency list and a queue to explore the tree level-by-level. It checks each neighbor for restrictions and previously visited status before enqueuing it.