Depth-First Search (DFS) | CodeSimulators

CORE INTUITION

The Stack: Down the Rabbit Hole

🕳️

Why a Stack?

DFS explores by going as deep as possible along each branch before backtracking. The call stack (implicit recursion) or an explicit stack (LIFO) naturally models this — push a node, explore its first unvisited neighbor, repeat until you hit a dead end, then pop back.

When to use: Path existence, cycle detection, topological sort, puzzle solving (mazes, Sudoku), connected components.

VISUALIZER

Interactive Grid Pathfinder (DFS)

Click empty cells to toggle walls (stone blocks). Watch the stack column as DFS pushes neighbors and pops them to search deeply.
Note: DFS is not suitable for shortest path grid traversal. It goes deep down a branch, resulting in a winding, suboptimal path. Compare this with BFS to see the contrast!

🧱

Simulation Status

Click Play or step forward to start.

LIFO CALL STACK (Bottom → Top)Depth: 1

(0,0)

Delay:400ms

RECURSION

The Stack Lifecycle & Order Hooks

Recursive DFS utilizes the system's execution call stack. This behaves exactly like an explicit stack data structure (Last-In, First-Out), saving node processing frames as we dive into subtrees.

Pre-Order Hooks

Actions executed before entering recursion calls. Used for path-building and pushing values down parameters (e.g., updating paths from root to leaves).

Post-Order Hooks

Actions executed after returning from children calls. Used to bubble up tree values, compute heights, or record topological orderings.

GRID DFS

Flood Fill & Grid Traversals

In 2D grid problems (like Number of Islands or Flood Fill), the grid cells behave exactly like graph vertices, and adjacent cells (Up, Down, Left, Right) are neighbors. DFS is highly efficient at sinking entire regions by recursively visiting and marking adjacent matched cells.

Grid Boundary Guards

When running recursion on grids, always check for boundaries first before accessing coordinates:if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== target) return;

BLUEPRINTS

Essential DFS Strategies

1. Recursive DFS

How it Works

Pushes node to recursive call stack.
Guards base cases immediately (null / already visited).
Recursively visits adjacent unvisited neighbors.
Backtracks naturally when executing frame pops.

dfsTemplate.js

function dfs(node, visited) {

if (visited.has(node)) return;

visited.add(node);

// Pre-order processing (work done on descent)

for (const neighbor of node.neighbors) {

dfs(neighbor, visited);

}

// Post-order processing (work done on backtracking)

}

2. Iterative DFS (Explicit Stack)

How it Works

Uses an explicit LIFO stack (array/list) instead of the call stack.
Pops current node, marks visited, and processes.
Pushes unvisited neighbors onto the stack (in reverse order to preserve original recursion sequence).
Eliminates recursive stack overflows on extremely deep trees or skewed graphs.

iterativeDfs.js

function iterativeDfs(startNode) {

const stack = [startNode];

const visited = new Set();

while (stack.length > 0) {

const node = stack.pop();

if (visited.has(node)) continue;

visited.add(node);

// Process node here

// Reverse neighbors list to maintain same traversal order as recursion

const neighbors = [...node.neighbors].reverse();

for (const neighbor of neighbors) {

if (!visited.has(neighbor)) {

stack.push(neighbor);

}

3. Directed Graph Cycle Detection

How it Works

Tracks nodes using 3 colors (White, Gray, Black).
Marks node as Gray (in current DFS recursion path).
If a neighbor is already Gray, a cycle has been discovered!
Marks node as Black once all neighbors are fully processed.

cycleDetection.js

function hasCycle(graph) {

const WHITE = 0, GRAY = 1, BLACK = 2; // Three color states

const states = new Map();

function dfs(node) {

states.set(node, GRAY); // In-process (visiting ancestors)

for (const neighbor of graph.get(node) || []) {

const neighborState = states.get(neighbor) || WHITE;

if (neighborState === GRAY) return true; // Found a back edge!

if (neighborState === WHITE && dfs(neighbor)) return true;

}

states.set(node, BLACK); // Fully processed

return false;

}

for (const node of graph.keys()) {

if ((states.get(node) || WHITE) === WHITE && dfs(node)) {

return true;

}

return false;

}

DFS vs BFS

When to Use Which

DFS (Stack)

Path existence (any path)
Topological sort (post-order)
Cycle detection (directed)
Backtracking / combination searches

BFS (Queue)

Shortest path (unweighted)
Level-order traversal
Topological sort (Kahn's)
Closest target in a grid

Memory Footprint: Width vs Depth

Space complexity of search algorithms depends on the shape of the search tree/graph:
• BFS Space Complexity: Bounded by the graph's maximum width (O(W)). For a perfect binary tree, the leaf level contains N/2 nodes, causing a worst-case space footprint of O(N) to hold the active level in the queue.
• DFS Space Complexity: Bounded by the graph's maximum depth (O(H)) because the call stack only retains active ancestors along the current search branch. For a balanced binary tree, the depth is O(log N), which is highly memory efficient!

APPLICATIONS

Real-world DFS Systems

1. Compiler Dependency Resolution

Problem: Compile project source files in the correct dependency order.
Core Logic: Compilers run Topological Sort using DFS. By performing DFS starting from any source file and pushing it to a stack on the post-order hook, we guarantee that all of a file's dependencies are processed and resolved before the file itself is compiled.

2. Git Merge Conflicts & Version History

Problem: Traverse commit branches to find cycles or common ancestral commits.
Core Logic: Git uses DFS to trace commit lines back to find the closest common ancestor commit (merge base) when executing merge actions, resolving branching lineages efficiently.

3. Puzzle Solving (AI Game Tree Analysis)

Problem: Evaluate subsequent moves in puzzles like Chess, Sudoku, or Tic-Tac-Toe.
Core Logic: Chess engines and puzzle solvers run recursive DFS (Minimax / alpha-beta pruning) to evaluate branch moves deeply to find the absolute winning sequence, backtracking when moves lead to losses.

PITFALLS

Common Mistakes

Marking Visited on Pop

In the iterative version, marking a node visited when it's popped (instead of when pushed) lets the same node get pushed onto the stack multiple times by different neighbors before it's ever processed — wasted work, and on grids it can duplicate entire branches.

Recursion Depth Limits

Recursive DFS on a long chain (a skewed tree, a linked-list-shaped graph) can blow the call stack. Python raises RecursionError past ~1000 frames by default. When depth isn't bounded, prefer the iterative, explicit-stack version.

Forgetting Visited Entirely

Skip the visited set and DFS on any graph with a cycle spins forever, re-entering the same nodes. Trees are safe without one (no cycles) — but grids and general graphs are not.

PRACTICE

Ready to Practice?

Number of IslandsMedium

Flood FillEasy

Max Area of IslandMedium

"DFS = stack (or recursion). Go deep, then backtrack."