Depth-First Search

What is Depth-First Search?

Depth-First Search, or DFS, follows one route as far as it can before returning to try another route. The unfinished route stays on a stack, either the language call stack or one we create ourselves.

You need to know recursion, stacks, and tree or graph nodes. The short version is: finish the current branch before moving to its sibling.

The Core Idea: Follow One Path

In LC 144: Preorder Traversal, the tree begins at 1, then has left subtree 2 with children 4 and 5, and right subtree 3 with children 6 and 7. Preorder visits 1, 2, 4, 5, 3, 6, 7.

Why does 4 appear before 3? Once DFS enters the left subtree, it finishes that whole subtree before returning to the root and taking the right edge.

It is like walking through a maze while keeping a trail of breadcrumbs. You keep taking one passage until it ends, then follow the trail back to the nearest untried turn.

How Recursion Follows a Branch

The Rule You Keep True

The stack contains the exact route from the start node to the node currently being processed. When a call returns, DFS resumes at the nearest node with unfinished work.

Traversal order tells us when to process the current node:

• Preorder processes the node before its children, which is useful when state must travel downward.
• Inorder processes a binary-tree node between its children, which returns sorted values for a BST.
• Postorder waits for both children, which is useful when the parent needs their answers.
• Graph DFS marks nodes visited and follows each unvisited neighbor.

Path Sum is the one that usually trips us up. The running sum belongs to one root-to-leaf path, so each recursive call needs its own path state or must undo shared state before trying the next child.

Picking the Right Shape

From Rule to Code

1. Handle the null, invalid, or already visited state first.
2. Mark the current state visited when cycles are possible.
3. Process the node before, between, or after recursive calls according to the needed order.
4. Recurse into each valid child or neighbor.
5. Return the summary the parent needs.

Every call either stops or moves to an unvisited state, so DFS finishes in O(V + E) time for a graph and uses stack space proportional to the deepest active path.