liveBook · Manning

Depth-first search

As explained in Algorithms Every Programmer Should Know

Depth-first search traverses a tree or graph by exploring a path as deeply as possible before backtracking to another branch.

Depth-first search (DFS) explores one path as far as possible, reaching a leaf before backtracking to another branch. A LIFO stack keeps track of where to continue. section 1.4.4 section 1.5

Searching for 8

Starting at root 5, DFS follows the first path down to a leaf. If 8 is not there, it returns to the nearest intersection and explores another path, continuing until it finds 8. section 1.4.4

In a tree, DFS takes O(V) time and uses space bounded by the tree’s depth, O(D). In a graph, track visited nodes to avoid cycles; graph traversal takes O(V + E). section 1.5

Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.

Compare DFS’s deep path with breadth-first search’s layer-by-layer sweep. section 1.4.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains stack-based traversal, backtracking, and complexity, then notes that graph searches need a visited set.
Examples
Traces a search from root 5 toward node 8, showing a deep path and subsequent backtracking.
What you can do after
Apply DFS to search a tree by exploring paths deeply and backtracking when needed.
How it connects
Contrasts with breadth-first search and connects to trees, graphs, stacks, and visited sets.

Also explained in

Compare how 9 books explain depth-first search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.