pattern heroPT–23LeetCode Extension

Depth-first search (DFS)

Go down one path as deep as you can, and at a dead end go back to the last fork. One walk visits everything connected to the start, and no place twice.

Variant
P14 Depth-first search (DFS)Tree nodes · 1×

Example problem: find the depth of a binary tree. Each node is an object with val, left and right; a missing child is none.

nonenonenonenonenonenone84121014call stacktop on the right8
not visited yetwaiting on the call stackcurrent callreturned, depth beside itnone: an empty child

8 is a node, not none: keep going

node = 8left = –right = –
01/42
restart · back · play · step
Speed
1function maxDepth(node):
2 if node is none:
3 return 0
4 left = maxDepth(node.left)
5 right = maxDepth(node.right)
6 return max(left, right) + 1

← → step · space play/pause

How to recognise

regions or islands in a grid, everything reachable from a start, all paths, or a tree problem solved from the leaves up.

How to solve problems like this

  1. Ask what a node needs from its children to know its own answer: a depth, a sum, a yes or no.
  2. Write f(node). If node is none, return the answer for an empty tree.
  3. Call f(node.left) and f(node.right), then combine the two answers with the node's own val.
  4. When information flows down instead (a running sum, the path so far), pass it as an argument.

Variant: Top-down

The same, but information flows downwards: a node gets what is known about the path from the root and passes it on to its children. Handy when the question is about the path from the root, not about a subtree.

  1. Ask what a node needs to know about the path above it: the sum so far, the number built so far, the allowed range.
  2. Pass it as an argument, updated with the node's own val, to both children.
  3. Decide at the leaves, then send the answer up: true if any child said true. You may return as soon as one does.
  4. Sum Root to Leaf Numbers passes number × 10 + val down and adds the numbers at the leaves.
  5. To validate a BST, pass the bounds down: the left child gets (low, node.val), the right one (node.val, high), and every val must fit its bounds.

Variant: Graph

The same, but in a graph several paths can lead to one vertex and there can be cycles. So visited vertices are marked, so as not to enter them again.

  1. Decide what a node is (a vertex, a cell, a state) and what its neighbours are.
  2. Write dfs(node): add it to visited first, then call dfs on every neighbour that is not visited yet.
  3. Start dfs from every node nobody has visited yet. Each start is a new connected part.
  4. To compute something, return it from dfs and combine what the calls below return: a size, a path, whether a target was found.

Variant: Grid

The same, but on a grid: cells are vertices and neighbouring cells are connected. A walk from a cell finds its whole region, such as a whole island.

  1. Decide what a node is (a cell, a vertex, a state) and what its neighbours are.
  2. Write dfs(node): mark it visited first, then call dfs on every unvisited neighbour.
  3. Start dfs from every node nobody has visited yet. Each start is a new region.
  4. To compute something, return it from dfs and combine what the calls below return: a size, a depth, a path.

Where it's used

  • Walking folders. find and du go into a folder, then into its first subfolder, and so on to the bottom, then come back. du adds up a folder's size from its subfolders' sizes: the tree's answer from its subtrees' answers.
  • Garbage collection. Java's garbage collector starts from the program's variables and follows references deep, marking everything alive. Whatever it never reaches is garbage.
  • Paint bucket. The fill tool in a paint program colours a cell and moves to its neighbours of the same colour until the area ends. The classic version is a depth-first walk over the area.