AlgoViz
HomeDepth-First Search

Introduction

Medium

Go deep first, back up when stuck

Problem

Learn depth-first search on trees and graphs: go as deep as possible along each branch before backtracking.

In simple words

Explore one path all the way down before trying the next.

The idea

Depth-first search follows one path as far as it goes, then backtracks and tries the next branch. On a tree that is just recursion; on a graph you also need a visited set, because unlike a tree a graph can lead you back where you started.

The trick

  • Trees need no visited set — graphs always do.
  • The recursion is the stack; an explicit stack does the same job iteratively.
  • O(V + E) when every node and edge is examined once.
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:
dfs from root
Output:
visits a whole branch first

Finished the walkthrough? Add it to your streak.