Depth-First Search

DFS is the single most reusable technique in this list. It is the default traversal for every tree problem, the backbone of most graph problems, and — once you notice that a sequence of decisions is a tree — the engine underneath backtracking as well.

It is also the technique people most often write from memory without understanding, which is why the same three bugs keep appearing.

One question per node#

The whole method is this: assume the recursive call already works on the children, and decide what you do with what it gives you. You never trace the recursion by hand. You write three things and trust them.

1. The base case. What is the answer for nothing at all? For a tree that is the empty node, and the answer is almost always 0, true, or null.
2. The recursion. Ask each child the same question.
3. The combination. Turn the children’s answers into this node’s answer.

Maximum depth is the smallest problem with all three: the depth of nothing is 0, ask both children, and the answer here is one more than the deeper of them.

Step through it and watch when the numbers appear. On the way down, nothing is computed — each call can only push another call and wait. Every value in the picture is produced on the way back up, which is what “post-order” means and why this shape suits any question whose answer at a node depends on its subtrees.

function depth(node):
    if node is null:
        return 0                              // base case: nothing is worth 0

    left  = depth(node.left)                  // trust the recursion
    right = depth(node.right)

    return 1 + max(left, right)               // combine

Every node is visited once, so it is O(n) time. Space is O(h) — the height of the tree — because that is how deep the call stack gets. For a balanced tree that is O(log n); for a tree degenerated into a chain it is O(n), which matters more often than people expect.

Diameter, balanced-or-not, and same-tree are all this template with a different combining line. That is worth taking literally: if you can state the base case and the combination in one sentence each, you have finished the problem.

The three orders#

Where you put the work relative to the two recursive calls gives three traversals, and each one is the right answer to a different kind of question.

• Pre-order — work, then left, then right. Information flows down. This is the order for copying or serialising a tree, because the root is emitted before anything that depends on it.
• In-order — left, work, right. On a binary search tree this visits the values in sorted order, which is the entire trick behind Kth Smallest Element in a BST and one way to validate a BST.
• Post-order — left, right, then work. Information flows up. This is the one above, and the default for anything aggregating over subtrees: heights, sums, counts, “is every subtree valid”.

The choice is not stylistic. Ask which direction the information moves — down from the root, or up from the leaves — and the order follows.

Down as well as up#

Some problems cannot be answered by return values alone, because a node’s correctness depends on where it sits, not just on what is under it. Then you pass context down as a parameter.

Validate BST is the standard example, and the standard wrong answer is to check that each node is between its two children. That is a local check, and it misses violations further down — a node deep in the left subtree can be larger than the root while still being larger than its immediate parent. The property is about the whole ancestor chain, so carry it:

function valid(node, low, high):
    if node is null:
        return true                           // an empty subtree can't break anything

    if not (low < node.value < high):
        return false

    return valid(node.left,  low, node.value)      // everything left must be < this
       and valid(node.right, node.value, high)     // everything right must be > this

The bounds narrow on the way down, and the invariant is that every node in a call is guaranteed to lie strictly inside (low, high). The initial call uses infinities, because the root is unconstrained.

The other mixed case is a problem where the answer might not pass through the root. Diameter is the classic: each call returns the height, but the longest path through the current node is left + right, which the parent does not want. Compute it, fold it into a running maximum held outside the recursion, and return the height regardless.

That distinction — what this node returns versus what this node contributes — is the one that separates the medium tree problems from the easy ones.

Graphs: the same shape, plus a visited set#

A graph is a tree that is allowed to have cycles, and cycles are the only new problem. Without a guard, DFS follows one round and recurses forever. With one, the traversal is identical.

visited = empty set

function visit(node):
    mark node as visited                     // on arrival, not on departure
    process node

    for next in neighbours(node):
        if next not visited:
            visit(next)

Mark on arrival. Marking after the loop, or marking a neighbour only once you get to it, lets two branches enter the same node before either has recorded it — which is an infinite loop on any cycle, and quadratic work even without one.

The cost is O(V + E): every vertex is entered once, and every edge is examined once from each end it is attached to.

The interactive DFS snippet builds exactly this traversal line by line in Go, over an adjacency list, and collects the visit order as it goes. It is worth stepping through once — the shape it ends on is the one every graph problem below is a variation of.

Two more things the tree version never had to think about:

• The graph may be disconnected. One call from one start node reaches one component. Counting components — which is what Number of Islands is really asking — means looping over every node and starting a fresh traversal from each one not yet visited.
• A node can be discovered from several directions. If a problem cares about which route you arrived by, DFS is the wrong tool; see BFS below.

Grids are graphs#

A grid problem is a graph problem where the adjacency list is implied: the neighbours of (r, c) are its four orthogonal cells, and you never build the edges — you compute them.

DIRS = [(-1,0), (1,0), (0,-1), (0,1)]

function fill(r, c):
    if r or c is out of bounds:  return       // guard first
    if grid[r][c] is not the target:  return  // wrong cell, or already handled

    grid[r][c] = new value                    // this is the "visited" mark

    for (dr, dc) in DIRS:
        fill(r + dr, c + dc)

Putting the bounds check at the top of the callee, rather than at each of the four call sites, is what keeps this short — one guard instead of four. Number of Islands is this with the outer loop that counts fresh starts; Flood Fill is this exactly, with one extra trap worth naming: if the replacement colour equals the starting colour, the “already handled” test never becomes true and the recursion never terminates. Check for it up front.

Overwriting the grid uses the input as the visited set, which is O(1) extra space and usually accepted. If the caller needs the grid intact, keep a separate visited structure and say why.

When recursion is the problem#

Recursion depth is bounded by the longest path, and on a 200×200 grid or a degenerate tree that can be tens of thousands of frames. Python’s default limit is 1000. Some interviewers ask for the iterative form for exactly this reason.

stack = [start]

while stack not empty:
    node = pop(stack)
    if node visited:  continue               // it may have been pushed more than once
    mark node as visited
    process node

    for next in neighbours(node):
        if next not visited:
            push next

Two differences from the recursive version are easy to miss. A node can be pushed several times before it is popped, so the visited check has to happen on pop as well as on push. And the children come off the stack in reverse order, so if the order of the output matters, push them reversed.

An explicit stack gives you pre-order naturally and post-order awkwardly. If your combination step needs the children’s answers, stay with recursion — the call stack is doing real work for you that you would otherwise have to rebuild by hand.

DFS or BFS?#

They visit the same nodes and cost the same. The difference is only the order, and one question settles it:

Does the answer involve distance? If the problem asks for the shortest path, the fewest moves, or anything measured in levels, use BFS — DFS will happily find a path, just not the shortest one. For everything else — does a path exist, how big is this component, aggregate something over a subtree — DFS is shorter to write and needs less memory on a deep, narrow structure. BFS is the safer choice on a shallow, wide one, where the queue stays small and the recursion would not.

Backtracking is DFS#

When the thing being searched is not a data structure but a space of decisions — which letters to place, which cells to step on next — the recursion tree is implicit and DFS still applies. The one addition is that a choice made on the way down has to be undone on the way out, because the next branch must start from a clean state:

function search(state):
    if state is a solution:  record it
    for choice in options(state):
        apply choice                          // mark
        search(next state)
        undo choice                           // and unmark on the way back

Word Search is the version that catches people: the cell you are standing on must be marked so the path cannot double back through itself, and unmarked as the call returns, so a different path is still free to use it. Forgetting the undo makes the first failed attempt poison the rest of the search. Backtracking covers this in its own right.

Recognising it#

Reach for DFS when:

• The input is a tree, and the answer at a node can be phrased in terms of its subtrees. This is nearly every tree problem on the list.
• The input is a graph or a grid, and the question is about reachability, connectivity, or component size rather than distance.
• You are asked to explore every possibility — subsets, permutations, paths through a board. That is backtracking, which is DFS over a decision tree.
• The problem mentions cycles, either to detect them or to avoid them. Either way it is a traversal with a visited set.

And the three bugs to check for before you say you are done: a missing base case, marking visited too late, and a recursion that returns the wrong quantity because the answer at a node and the value its parent needs are not the same thing.

Summary#

Write the base case, trust the recursive call, and combine. Which side of the recursive calls your work sits on decides whether information flows down from the root or up from the leaves, and that choice is the whole design. On graphs, add a visited set and mark on arrival; on grids, compute the neighbours instead of storing them; on decision spaces, undo each choice on the way out. It is one template, and after enough repetitions the only part still requiring thought is what a single node owes its parent.