AlgoViz
HomeDepth-First Search

Fundamentals

Medium

Base case, process, recurse

Problem

Understand the DFS recursion template: base case, process the node, recurse on each child/neighbour.

In simple words

Handle the current spot, then dive into each neighbour the same way.

The idea

Every DFS has the same skeleton: stop at the base case, do whatever this node needs, then recurse into each neighbour. Whether the work happens before or after the recursive calls is what makes it top-down or bottom-up.

The trick

  • Work before recursing = preorder, work after = postorder.
  • Return early on null or an already-visited node.
123456

Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.

1/8
Optimal
timeO(n)spaceO(h)

Post-order combine.

1function depth(node) {2  if (!node) return 0;3  return 1 + Math.max(depth(node.left), depth(node.right));4}

Input

nodes
6, 5 edges

Output

max depth
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
count nodes via dfs
Output:
n

Finished the walkthrough? Add it to your streak.