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.
1var reachableNodes = function(n, edges, restricted) {
2 const restrictedSet = new Set(restricted);
3 const adjList = Array.from({length: n}, () => []);
4 for (const [a, b] of edges) {
5 adjList[a].push(b);
6 adjList[b].push(a);
7 }
8
9 const dfs = (node, visited) => {
10 if (restrictedSet.has(node) || visited.has(node)) return 0;
11 visited.add(node);
12 let count = 1;
13 for (const neighbor of adjList[node]) {
14 count += dfs(neighbor, visited);
15 }
16 return count;
17 };
18
19 return dfs(0, new Set());
20};JavaScript implementation uses an adjacency list created from an array of arrays and utilizes Sets to handle visited and restricted nodes. The DFS function recursively computes reachable 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 Java code employs a queue to realize the BFS traversal, updating visited nodes on each iteration and ignoring restricted nodes while expanding from node 0.