Reachable Nodes With Restrictions - Video Solutions

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.