There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes.
Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.
Note that node 0 will not be a restricted node.
Example 1:
Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] Output: 4 Explanation: The diagram above shows the tree. We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1] Output: 3 Explanation: The diagram above shows the tree. We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.
Constraints:
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges represents a valid tree.1 <= restricted.length < n1 <= restricted[i] < nrestricted are unique.Problem Overview: You are given an undirected tree with n nodes labeled from 0 to n-1. Starting from node 0, count how many nodes you can visit without stepping into any node listed in the restricted array. Once a restricted node is encountered, traversal must stop before entering it.
The structure is a tree, so there is exactly one path between any two nodes. The main task is to traverse the graph while skipping restricted nodes and avoiding revisits. A set for fast restriction lookup and an adjacency list for the graph representation make the traversal efficient.
Approach 1: DFS Using Adjacency List (Time: O(n), Space: O(n))
Build an adjacency list from the edge list to represent the tree. Store all restricted nodes in a hash set for O(1) membership checks. Start a Depth‑First Search from node 0, and recursively explore neighbors that are not restricted and not yet visited. Each node is processed once, and each edge is examined at most twice. DFS works well because trees have no cycles other than the parent link, so a visited set prevents backtracking loops.
This approach is concise and natural for recursive traversal. During DFS, increment a counter whenever a valid node is visited. The recursion stops immediately if the next node appears in the restricted set. This solution uses the classic depth-first search technique on a graph representation.
Approach 2: BFS Using Adjacency List (Time: O(n), Space: O(n))
Instead of recursion, perform a level‑order traversal using a queue. Initialize the queue with node 0 and repeatedly pop nodes while pushing valid neighbors. Before adding a neighbor, check two conditions: it must not be restricted and must not have been visited before. Each node enters the queue at most once, which keeps the runtime linear.
BFS processes nodes level by level, which makes it easy to reason about traversal order and avoids recursion stack limits. The adjacency list still provides efficient neighbor iteration. This approach applies the standard breadth-first search pattern used for many reachability problems.
Recommended for interviews: Either DFS or BFS with an adjacency list is the expected solution. Both run in O(n) time and demonstrate that you understand graph traversal and constraint filtering. DFS is slightly shorter to implement, while BFS avoids recursion and is sometimes preferred in production systems. Showing both approaches demonstrates strong understanding of graph traversal fundamentals.
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.
This approach builds an adjacency list from the input edges, then performs a DFS starting from node 0. It skips over restricted nodes and ensures each node is visited only once. The count of nodes reached is returned as the answer.
Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.
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.
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.
Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.
First, we construct an adjacency list g based on the given edges, where g[i] represents the list of nodes adjacent to node i. Then we define a hash table vis to record the restricted nodes or nodes that have been visited, and initially add the restricted nodes to vis.
Next, we define a depth-first search function dfs(i), which represents the number of nodes that can be reached starting from node i. In the dfs(i) function, we first add node i to vis, then traverse the nodes j adjacent to node i. If j is not in vis, we recursively call dfs(j) and add the return value to the result.
Finally, we return dfs(0).
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
Python
Java
C++
Go
TypeScript
Similar to Solution 1, we first construct an adjacency list g based on the given edges, then define a hash table vis to record the restricted nodes or nodes that have been visited, and initially add the restricted nodes to vis.
Next, we use breadth-first search to traverse the entire graph and count the number of reachable nodes. We define a queue q, initially add node 0 to q, and add node 0 to vis. Then we continuously take out node i from q, accumulate the answer, and add the unvisited adjacent nodes of node i to q and vis.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS Approach Using Adjacency List | Time Complexity: O(n) because each node is visited once. |
| BFS Approach Using Adjacency List | Time Complexity: O(n) because each node is processed once using BFS. |
| DFS | — |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Using Adjacency List | O(n) | O(n) | Best general approach for tree traversal. Concise implementation and common in coding interviews. |
| BFS Using Adjacency List | O(n) | O(n) | Useful when avoiding recursion or when level-by-level traversal is preferred. |
Leetcode 2368. Reachable Nodes With Restrictions | WeeklyContest 305. Medium • Code with Alisha • 1,588 views views
Watch 9 more video solutions →Practice Reachable Nodes With Restrictions with our built-in code editor and test cases.
Practice on FleetCode