Reachable Nodes With Restrictions

Reachable Nodes With Restrictions

What is this problem about?

The Reachable Nodes With Restrictions problem gives you a tree and a set of restricted nodes. Starting from node 0, count how many nodes are reachable without passing through any restricted node. This coding problem uses BFS/DFS with restricted node pruning. The array, union find, BFS, hash table, graph, DFS, and tree interview pattern is demonstrated.

Why is this asked in interviews?

MakeMyTrip asks this to test BFS/DFS with conditional traversal — the restricted nodes act as walls, and you must count reachable nodes before hitting any restriction.

Algorithmic pattern used

BFS/DFS with restricted set. Build adjacency list. BFS/DFS from node 0: don't visit nodes in the restricted set and don't traverse through them. Count all visited nodes.

Example explanation

n=7, edges=[(0,1),(1,2),(3,1),(4,0),(0,5),(5,6)], restricted=[4,5]. BFS from 0: add 0. Neighbors: 1(not restricted)→add, 4(restricted)→skip, 5(restricted)→skip. From 1: neighbors 0(visited),2→add,3→add. From 2: no unvisited. From 3: no unvisited. Count = {0,1,2,3} = 4.

Common mistakes candidates make

• Visiting restricted nodes to block paths (must skip entirely, not just not count).
• Not using a visited set (infinite loop on cycles? No, trees can't cycle, but adjacency list may revisit).
• Traversing through restricted nodes to find nodes beyond them.
• Not handling node 0 being in the restricted set.

Interview preparation tip

Reachable Nodes With Restrictions is straightforward BFS/DFS with a blocked node set. The critical rule: restricted nodes are barriers, not just non-countable nodes — don't traverse their edges. Practice similar "BFS with obstacles" problems. The distinction between "don't count this node" and "don't traverse through this node" is a common interview trap.