BFS/DFS Graph and Tree Traversal and Shortest Paths

What's being tested

Candidates must demonstrate correct use of BFS and DFS for traversal, reachability, and component counting, plus shortest-path techniques (unweighted BFS, Dijkstra) under constraints. Interviewers probe algorithmic tradeoffs (time/space), correctness with blocked/forbidden nodes, and iterative vs recursive implementations to avoid stack overflow.

Patterns & templates

• BFS for shortest paths in unweighted graphs — use deque queue, mark visited on enqueue, time O(V+E), space O(V).

• DFS (recursive or explicit stack) for connectivity and nested structures; prefer iterative stack to avoid recursion depth issues.

• Dijkstra with heapq for weighted shortest paths; complexity O((V+E) log V); store distances and parents for path reconstruction.

• Multi-criteria shortest path: encode tuple cost (danger_count, steps) and use lexicographic comparison in priority queue or use 0-1 BFS for binary costs.

• Remove/ignore blocked nodes by pre-marking in set or deleting adjacency entries before traversal.

• Connected clusters (geometric): build adjacency by threshold distance squared to avoid sqrt, deduplicate coordinates with a set, then BFS/DFS for components.

• Deleting in a binary search tree: handle leaf, single-child, two-children cases — replace with inorder successor (min in right subtree) and adjust pointers.

Common pitfalls

Pitfall: Marking visited only on pop instead of on enqueue causes duplicate enqueues and exponential blowup on dense graphs.

Pitfall: Using sqrt for many distance checks costs CPU and risks floating error — compare squared distances instead.

Pitfall: Recursing on deeply nested lists/trees without converting to an iterative stack risks stack overflow on large inputs.