Iterative Deepening DFS (IDDFS) Visualization

Q: Why use IDDFS instead of BFS?

IDDFS needs memory O(b·d) instead of O(b^d) while still finding the shallowest solution.

About this visualization

Iterative deepening runs depth-limited DFS with limits 0, 1, 2, … until the goal is found. It returns the shallowest goal like BFS but stores only the current path like DFS. The shallow nodes are visited again in each iteration, but that repeated work is small compared with the deepest level.

How it works

Run DFS but do not go deeper than the limit L, starting with L = 0.
If the goal is not found, increase L by one and start over.
The first L that reaches the goal gives the shallowest solution.

Formulas used

Time: $O(b^{d})$ Space: $O(b\cdot d)$

Worked example

On the 15-node binary tree with goal K at depth 3, iteration 0 visits only A, iteration 1 visits A, B, C, iteration 2 reaches depth 2, and iteration 3 finds K on the path A → B → E → K. The root is visited four times in total — the price paid for memory proportional to the depth only.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst case	$O(b^{d})$
Space	$O(b\cdot d)$

Complete. Optimal in number of edges (cost-optimal when all steps cost the same). Re-visits shallow nodes every iteration.

When to use it

Searching when the depth of the solution is unknown and memory is limited.
Game-tree search with time limits.
Understanding the time-space trade-off between BFS and DFS.

Frequently asked questions

Why use IDDFS instead of BFS?

IDDFS needs memory $O(b\cdot d)$ instead of $O(b^{d})$ while still finding the shallowest solution.

Isn't repeating the search wasteful?

Slightly, but most nodes are at the bottom level, so the repeated shallower levels add only a small constant factor to $O(b^{d})$ .

Is IDDFS optimal?

It is optimal in number of edges (and in cost when all step costs are equal).