Iterative Deepening Search: DFS Memory With BFS Guarantees

The core idea: DFS pretending to be BFS

Breadth-first search finds the shallowest goal but pays for it in space: its FIFO frontier can hold the entire last level, O(bᵈ) nodes, where b is the branching factor and d the depth of the shallowest goal. Depth-first search is frugal — O(bm) space for a tree of maximum depth m — but it is neither optimal (it returns the first goal it stumbles into, not the shallowest) nor complete when the tree is infinite (it can dive down one branch forever).

Iterative deepening buys BFS's guarantees using DFS's memory. The trick is depth-limited search (DLS): run an ordinary recursive DFS, but refuse to expand any node at depth ≥ some limit L. IDDFS simply calls DLS with L = 0, 1, 2, 3, … until a goal is found:

function IDDFS(root, isGoal):
  for limit = 0 to ∞:
    found = DLS(root, isGoal, limit)
    if found ≠ NULL: return found   // shallowest goal

function DLS(node, isGoal, limit):
  if isGoal(node): return node
  if limit == 0:   return NULL       // cutoff, not failure
  for child in successors(node):
    r = DLS(child, isGoal, limit-1)
    if r ≠ NULL: return r
  return NULL

The key invariant: when the loop reaches limit L, DLS has explored exactly the set of nodes reachable within L edges of the root — the same set BFS would have expanded by the time it finishes level L. Because the outer loop tries limits in increasing order, the first limit at which a goal appears is d, so IDDFS returns a shallowest goal — optimal for unit-cost edges, exactly like BFS.

Why re-doing the work is nearly free

The obvious objection: won't re-running DFS from the root at every limit waste an enormous amount of time? Surprisingly, no — because the work is dominated by the last level, and the last level is only done once.

In a uniform tree with branching factor b, level i holds bⁱ nodes. On the final iteration (limit d), the root is generated once but re-expanded d+1 times, the level-1 nodes d times, and so on; the leaf level is generated exactly once. The total node generation count is

N(IDDFS) = (d+1)·b⁰ + d·b¹ + (d−1)·b² + … + 1·bᵈ
         = Σ (from i=0 to d) (d−i+1)·bⁱ

This sum is bounded by bᵈ · (b/(b−1))², so it is Θ(bᵈ) — the same asymptotic cost as a single BFS. The overhead factor versus one pass of BFS is roughly b/(b−1):

• b = 2: ratio ≈ 2 — worst case, but still just a constant.
• b = 10: ratio ≈ 1.11 — about 11% overhead.
• b = 25: ratio ≈ 1.04 — a wide game tree; overhead is a rounding error.

The intuition: an exponential series is dominated by its largest term. Everything above the leaf level sums to a bounded fraction of the leaf-level cost, so the repeated shallow work is asymptotically negligible. The higher the branching factor, the more each level dwarfs the one above it, and the cheaper the repetition becomes.

Complexity, tight

Let b = branching factor and d = depth of the shallowest goal.

• Time: O(bᵈ). Derived above; the leading constant is b/(b−1) relative to BFS, which for b ≥ 3 is ≤ 1.5×.
• Space: O(bd) if you store the frontier of the current node's siblings along the path, or O(d) if you regenerate children on the fly and keep only the recursion stack. Either way it is linear in depth — the whole point.
• Completeness: yes, for finite b, even on infinite-depth trees, because every finite depth is eventually tried.
• Optimality: yes for uniform (unit) edge costs, since it finds a shallowest goal first. For non-unit costs it is not optimal — that requires the cost-based variant below.

Compare the alternatives on the same tree: BFS is O(bᵈ) time but O(bᵈ) space; DFS is O(bm) space but explores O(bᵐ) nodes and may miss the shallow goal entirely, where m can be ≫ d or even ∞. IDDFS keeps the good column from each: BFS's time and optimality, DFS's space. The one thing it gives up is node re-generation, and we just showed that costs a constant factor.

A subtle caveat: this analysis assumes a tree. On a general graph with cycles or many paths to a node, naive IDDFS re-explores duplicate states and can blow up to exponential even when the graph is small — see the pitfalls section.

IDA*: iterative deepening for optimal costed search

The most important descendant of IDDFS is Iterative Deepening A* (IDA*), also from Korf's 1985 paper. Plain A* is optimal and often the fastest way to find least-cost paths, but its OPEN and CLOSED lists store O(bᵈ) nodes — the same memory wall BFS hits. IDA* applies the iterative-deepening idea to A*'s f = g + h evaluation instead of to raw depth.

• Instead of a depth limit, use an f-cost threshold t, starting at t = h(root).
• Run a depth-first search that prunes any node whose f = g + h exceeds t.
• If no goal is found, set t to the minimum f-value that exceeded the old threshold and search again.

With an admissible heuristic (never overestimates), IDA* returns an optimal-cost solution while using only O(d) memory. It was the algorithm that first solved random instances of the 15-puzzle (≈10¹³ states) optimally, and later powered admissible-heuristic solvers for Rubik's Cube. The engineering lesson generalizes: when A* runs out of RAM before it runs out of time, iterative deepening on the cost bound trades a constant factor of recomputation for a linear-space footprint.

Where it actually runs

Iterative deepening earns its keep exactly when the frontier won't fit in memory or the maximum depth is unknown:

• Game-tree search. Chess and other minimax/alpha-beta engines almost universally use iterative deepening as a wrapper: search to depth 1, then 2, then 3, until the clock runs out. Two bonuses fall out for free — you always have a legal move ready (anytime behavior), and the best move from depth k−1 seeds move ordering at depth k, which dramatically sharpens alpha-beta pruning. The 're-search' cost is trivial because game trees are exponential in depth.
• Puzzle and pathfinding solvers. IDA* remains the standard for optimal 15-puzzle, 24-puzzle, and Rubik's-Cube solving where storing the frontier is impossible.
• Interpreters and provers. Prolog-style depth-first resolution can loop forever; iterative-deepening search over the SLD tree gives a complete strategy without the memory of breadth-first resolution. Similar patterns appear in some theorem provers and program-synthesis search.
• Anytime / real-time systems. Any search under a deadline benefits: each completed iteration is a valid answer of increasing quality, so you can stop whenever time expires and return the best result so far.

Pitfalls, edge cases, and variants

Graphs with repeated states. The clean b/(b−1) overhead assumes a tree. On a graph where many paths lead to the same node, tree-style IDDFS re-expands each duplicate, and cost can explode. Fixes: a visited set for the current path (cheap, kills only cycles), or a transposition table / bounded cache of seen (state, depth) pairs — which reintroduces some memory but bounds the damage. There is a genuine tension here: full duplicate detection is what BFS pays memory for, and IDDFS's whole selling point is not paying it.

Non-unit edge costs. Plain IDDFS optimizes for fewest edges, not least cost. For weighted graphs use IDA* (heuristic) or iterative-deepening on a cost bound; incrementing the bound by too little wastes iterations, by too much loses optimality.

Real-valued costs and threshold thrash. If f-values are continuous, IDA* can raise the threshold by a minuscule amount each pass and do many near-identical searches — pathologically slow. Remedies include a small ε bump, RBFS (recursive best-first search), or bucketed thresholds.

Off-by-one at the limit. A classic bug: the base case must distinguish 'cutoff' (hit the depth limit) from 'failure' (exhausted subtree). If you don't, IDDFS may report failure at limit d even though deeper goals exist, and never try a larger limit. Track a cutoff-occurred flag; only stop deepening when a whole iteration completes with no cutoff and no goal.

When to reach for it — and when not

Use iterative deepening when the branching factor is moderate-to-large, the goal depth is unknown, and the frontier is too big for RAM. This is precisely the regime — huge or infinite trees, unit costs, memory-bound — where BFS dies of memory and DFS gives wrong answers. The higher b, the more attractive IDDFS becomes, because the re-expansion overhead shrinks toward zero.

Skip it when:

• The frontier fits comfortably in memory — plain BFS or A* is simpler and never re-generates nodes.
• The state space is a dense graph with heavy duplication and no cheap way to prune repeats — the re-expansion penalty can go exponential.
• Node generation is expensive (each expansion hits disk or a network) — here re-doing shallow work isn't free in wall-clock terms, and you'd rather pay memory to avoid recomputation.
• You need least-cost with wildly varying edge weights and no good heuristic — uniform-cost search (Dijkstra) may be the better fit despite its memory.

The mental model to keep: IDDFS is not a clever hack, it's a principled point on the time–space trade-off curve. It converts a factor-of-bᵈ space cost into a factor-of-b/(b−1) time cost. For any exponential tree with a decent branching factor, that is one of the best trades in all of algorithm design.

IDDFS versus the two searches it sits between, on a tree with branching factor b and shallowest goal at depth d.

Property	BFS	DFS	IDDFS
Time	O(bᵈ)	O(bᵐ)	O(bᵈ)
Space	O(bᵈ)	O(bm)	O(bd)
Shortest path (unit)	Yes	No	Yes
Complete (infinite depth)	Yes	No	Yes
Repeats work?	No	No	Yes (~b/(b−1)×)