Skip to main content
Talentd

Reachable Nodes With Restrictions - Solution & Explanation

MediumArrayHash TableTreeDepth-First Search24 min readAsked at: Google, MakeMyTrip
Practice this problem

Problem Statement

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 <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.
  • 1 <= restricted.length < n
  • 1 <= restricted[i] < n
  • All the values of restricted are unique.

Approach Overview

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.

Approach 1: DFS Approach Using Adjacency List

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.

Try this approach in the editor →

Approach 2: BFS Approach Using Adjacency List

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.

Try this approach in the editor →

Approach 3: DFS

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: BFS

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS Approach Using Adjacency List

Time Complexity: O(n) because each node is visited once.
Space Complexity: O(n) for storing the adjacency list and visited nodes information.

BFS Approach Using Adjacency List

Time Complexity: O(n) because each node is processed once using BFS.
Space Complexity: O(n) for adjacency list and other arrays.

DFS—
BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Using Adjacency ListO(n)O(n)Best general approach for tree traversal. Concise implementation and common in coding interviews.
BFS Using Adjacency ListO(n)O(n)Useful when avoiding recursion or when level-by-level traversal is preferred.

Video Solution

Leetcode 2368. Reachable Nodes With Restrictions | WeeklyContest 305. Medium • Code with Alisha • 1,636 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reachable Nodes With Restrictions easy or hard?
Reachable Nodes With Restrictions is generally classified as a Medium problem. The logic relies on standard DFS or BFS traversal, but the restricted node constraint requires careful filtering during traversal and correct graph construction.
How to solve Reachable Nodes With Restrictions in O(n)?
Construct an adjacency list from the edge list and store restricted nodes in a hash set. Start DFS or BFS from node 0, and only visit neighbors that are not restricted and not already visited. Because the graph is a tree with n−1 edges, the traversal processes each node once, achieving O(n) time.
What is the best approach for Reachable Nodes With Restrictions?
The best approach is graph traversal using either DFS or BFS with an adjacency list. Store restricted nodes in a hash set for O(1) checks and traverse from node 0 while skipping restricted nodes. Since the graph is a tree, each node is visited at most once, giving an O(n) time solution.
Is Reachable Nodes With Restrictions asked at Google/Amazon/Meta?
Graph traversal problems with constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving restricted nodes, blocked vertices, or reachability in trees are common because they test DFS/BFS fundamentals and graph modeling skills.
What data structure is used in Reachable Nodes With Restrictions?
The solution typically uses an adjacency list to represent the graph, a hash set to store restricted nodes for constant-time lookups, and either a recursion stack (DFS) or queue (BFS) for traversal. A visited set or boolean array prevents revisiting nodes.
What is the time complexity of Reachable Nodes With Restrictions?
The optimal solution runs in O(n) time where n is the number of nodes. Building the adjacency list takes O(n), and the DFS or BFS traversal also visits each node once. Space complexity is O(n) due to the adjacency list, visited tracking, and recursion stack or queue.
Reachable Nodes With Restrictions Python or Java solution approach?
Both Python and Java implementations follow the same structure: build an adjacency list, place restricted nodes in a set, and run DFS or BFS from node 0. Python often uses recursion or collections.deque for BFS, while Java uses ArrayList for adjacency lists and a Queue for traversal.

Ready to solve this problem?

Practice Reachable Nodes With Restrictions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Jumps to Reach Home

Next

Open the Lock