Watch this grid. Three islands, and DFS picks one cell and floods outward -- but not evenly like BFS. It races down one direction as far as it can go, hits a dead end, then reverses course and tries the next direction. The island fills in a snaking, aggressive pattern rather than a smooth wavefront.

This is the core personality of DFS: commit fully, then undo. Where BFS is cautious and level-headed (exploring every neighbor at distance 1 before any at distance 2), DFS is bold and reckless -- it dives to the deepest reachable cell before considering alternatives. When it runs out of road, it backtracks: it rewinds to the last decision point where an unexplored direction still exists, and dives again.

That backtracking behavior is not just a quirk. It is the exact same mechanism behind recursive backtracking algorithms -- subset generation, permutation enumeration, N-Queens, Sudoku solving. DFS is backtracking, wearing a graph-traversal costume. Once you see the connection, a huge class of “generate all X” problems collapses into the same pattern: go deep, hit a wall, undo the last choice, try the next option.

DFS tracks each node in one of three states: white (unvisited), gray (on the recursion stack -- actively being explored), and black (fully processed -- all descendants explored and returned from). Tap each node below to cycle through the three DFS states. Gray means “I'm still on the recursion stack.” Black means “I'm done -- move along.”

Four islands hide in this grid. Your job: find each one by tapping an unvisited land cell to start DFS.

Here is the key observation: when you start DFS from any land cell, it floods the entire connected island before returning. Every reachable land cell gets marked visited. That means when DFS finishes, you know every cell belonging to that island has been accounted for. The next time your outer scan hits an unvisited land cell, it must belong to a different island.

This is the Number of Islands algorithm (LC 200) in its entirety: scan every cell in the grid. When you find unvisited land, increment the count and run DFS to mark the whole island visited. The count at the end is the number of islands. No adjacency list. No graph construction. Just a nested loop and a recursive flood.

If DFS “is” backtracking, where does the backtracking actually happen? The answer is hiding in the call stack.

Every recursive DFS call pushes a new frame onto the stack. Every return pops one off. At any moment, the call stack holds exactly the nodes on the path from the root to the current node -- your “trail of breadcrumbs.” When DFS finishes exploring a subtree and returns, the stack automatically rewinds to the parent. That return is the backtrack step.

This is why recursive DFS is so clean: you do not need to manually undo your last choice. The language runtime does it for you through the call/return mechanism. When you later write iterative DFS with an explicit stack, you will have to do this bookkeeping yourself -- but the principle is identical.

Step through the tree below and watch the stack mirror the path from root to current node. Notice how a return (pop) always takes you back to the last decision point with unexplored children.

DFS on a grid tries neighbors in a fixed order: up, right, down, left. At each cell, it attempts the first direction. If that direction leads to a valid unvisited cell, DFS immediately recurses there -- going deeper. It does not check the other three directions yet. Those wait on the call stack until the deeper exploration backtracks.

This is the mental model to internalize: DFS always takes the first available exit and commits to it. Only when that path is exhausted does it return and try the second exit, then the third, then the fourth. The order of neighbor iteration determines the exact traversal path.

Tap the cell you think DFS visits next. The stack on the right shows your current path -- and when DFS backtracks, you will see the stack shrink.

Every DFS traversal implicitly builds a decision tree. On the left is the graph DFS is exploring. On the right is the tree of recursive calls it makes.

Each node in the decision tree represents a recursive call: “I'm at node X, considering its neighbors.” Each branch is a direction DFS chose to explore. When DFS encounters an already-visited node, that branch gets pruned (marked X) -- it returns immediately without recursing further. When all branches from a node are either pruned or fully explored, DFS backtracks: it returns to the parent, which is literally “going up a level” in the decision tree.

This is the connection that makes DFS and backtracking the same algorithm. Subset generation builds the same tree shape -- each level decides “include this element or not.” Permutation generation branches on “which element goes in this position.” The pruning condition changes, but the structure is identical: recurse, prune, backtrack.

Step through and watch both views update in sync.

Islands are grids with implicit edges between adjacent cells. But the “outer loop + DFS flood” pattern does not care about the shape of the graph. It works on any structure where you need to find connected components.

A social network with clusters of friends. A circuit board with groups of connected pins. A dependency graph with independent modules. In every case, the algorithm is the same: scan all nodes, run DFS from each unvisited one, count the number of times you started a new DFS. The graph representation changes; the pattern does not.

Here are three disconnected components in an explicit graph. Tap each unvisited node to run DFS and count them.

Not every graph problem calls for exhaustive DFS. Shortest path on an unweighted graph? That is BFS territory. Minimum spanning tree? That is greedy. Exhaustive DFS shines when you need to visit everything reachable from a starting point -- flood fill, connected components, cycle detection, topological sort preprocessing.

The tell: if the problem asks “how many groups” or “mark everything connected to X” or “does a path exist” (without caring about shortest), DFS is likely the tool. If the problem asks “what is the shortest/cheapest way,” you probably need BFS or Dijkstra instead.

For each problem below, decide: exhaustive DFS, or a different tool?

You have watched DFS flood islands, traced the call stack, and identified connected components. Now construct the code yourself.

Number of Islands (LC 200) is one of the most commonly asked graph problems in technical interviews -- and one of the most instructive to build from scratch, because the two-function structure (outer scan + inner flood) is a template that transfers directly to dozens of grid problems. Surrounded Regions (LC 130), Pacific Atlantic Water Flow (LC 417), Max Area of Island (LC 695) -- they all use the same outer-loop-plus-DFS-flood skeleton. The only difference is what the inner function does when it visits a cell: count area, mark a region, check connectivity to a boundary.

The reason this exercise asks for four blanks across two functions, rather than filling one function, is that the conceptual split between “where to start DFS” and “what DFS does” is the whole algorithm. The outer function's job is simple but critical: scan every cell, and when you find unvisited land, that is a new island -- increment the count and flood it. The inner function's job is recursive: mark the current cell, then try all four directions. If a direction leads to valid unvisited land, recurse there. If not, do nothing -- the base case is implicit.

Four blanks test four distinct decisions: how to detect unvisited land, when to call the flood function, how to prevent revisiting a cell, and how to recurse in all four directions.

Four questions that tie the whole lesson together.

The mental models from this lesson -- DFS as exhaustive flood, the call stack as a trail of breadcrumbs, the decision tree as an explicit map of recursive choices -- are not just explanations of DFS. They are thinking tools that you will reach for every time you see a new graph problem. When someone asks “can you find all connected components?”, the flood model tells you: scan for unvisited nodes, DFS from each one, count the scans. When someone asks “can you enumerate all subsets?”, the decision tree model tells you: each level is a binary choice (include or exclude), and DFS explores every branch.

The connection between DFS and backtracking is the deepest takeaway. They are not two separate algorithms that happen to use recursion. They are the same algorithm applied to different domains. DFS on a graph visits every reachable node. Backtracking on a search space visits every reachable state. The pruning condition changes, but the mechanism -- recurse, hit a wall, return to the last choice point -- is identical.

These are not recall questions. Each one asks you to apply the mental models you built -- the flood pattern, the stack-as-breadcrumbs insight, and the decision tree -- to a scenario you have not seen yet.