BFS gets the shortest path in an unweighted graph by paying for it with memory — the whole frontier, one full layer of the graph, has to sit in the queue at once. DFS gets the memory back — just a stack, at most one path deep — by giving up the shortest-path guarantee entirely. Iterative Deepening DFS asks for both: run a depth-limited DFS that refuses to go past depth 0, then depth 1, then depth 2, and so on. The first time one of these limited searches reaches the goal at all, that's provably the fewest possible steps — no shallower limit could have found it, or an earlier iteration already would have. Each individual iteration is still just DFS with a stack, so peak memory never exceeds the current depth limit. The bill comes due elsewhere: every iteration re-walks all the shallow ground the previous ones already covered, from scratch. This page's own demo measures that redundant cost directly rather than just asserting it exists. (A different site entry, Iterative Deepening Search, applies this exact same "repeat a depth-limited search, one deeper limit at a time" idea to game trees, scoring cut-off positions with a heuristic instead of testing plain reachability — same outer loop, a minimax search glued on where this page has a maze.)
Click any cell to toggle a wall (green is the start, orange is the end — fixed). Step through the search and watch two things at once: the current path strip below the grid (this iteration's DFS stack — never longer than the current depth limit) and the stats line above it, which keeps a running total across every iteration so far. Watch that total climb far faster than the number of distinct cells in the maze — that's the redundant re-exploration, made concrete instead of asserted. Edit the walls and press Reset to see the effect on a maze of your own choosing; opening up enough cycles can push the total into the thousands, at which point the demo stops itself early rather than trying to animate all of it (see the log for a note when that happens).
A depth-limited DFS is plain DFS with one extra rule: once the current path reaches the limit, stop descending and back up, exactly as if every cell at that depth had no unexplored neighbors. Run it once with limit 0 — it only ever looks at the start cell. Run it again with limit 1, from scratch — now it can also reach the start's direct neighbors. Keep raising the limit by exactly one each time and every iteration explores precisely the set of cells reachable within that many steps, no more. The moment an iteration's depth-limited search reaches the goal, the limit it's currently running at is the shortest distance — every smaller limit was already tried and failed, so nothing shorter exists, and this iteration is the first to succeed. That's the same guarantee BFS makes, arrived at from the opposite direction: BFS explores layer-by-layer within a single pass and keeps the whole current layer in memory to do it; IDDFS explores layer-by-layer across many passes and only ever needs to remember one root-to-current path within a single pass.
The redundant work is real, not incidental. Iteration for limit k revisits every
cell iteration k-1 already found, then goes one layer further — so the shallow cells
near the start get walked over and over, once per remaining iteration. Iterative Deepening Search's own Why it works
section derives the resulting bound precisely: for a search tree with branching factor
b, the deepest iteration alone accounts for roughly a b/(b-1) fraction of
the total work across all iterations combined, so the overhead shrinks as branching goes up (a
wide, bushy graph wastes proportionally less) and grows as branching drops toward 1 (a long thin
corridor with no side branches wastes proportionally more, since there's nothing for a deeper
iteration to dwarf the shallow ones with).
The inner search, depth-limited DFS. The one line that makes it depth-limited instead of
plain DFS is the depth === limit check — and note it's checked after the
goal test, not before (see Pitfalls):
function depthLimitedSearch(grid, rows, cols, start, end, limit) {
const key = (r, c) => r * cols + c;
const onPath = new Array(rows * cols).fill(false);
const endKey = key(...end);
let foundPath = null;
function dfs(node, depth, path) {
if (node === endKey) { foundPath = path.slice(); return true; }
if (depth === limit) return false;
onPath[node] = true;
const r = Math.floor(node / cols), c = node % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (onPath[nk] || grid[nk] === WALL) continue;
path.push(nk);
if (dfs(nk, depth + 1, path)) { onPath[node] = false; return true; }
path.pop();
}
onPath[node] = false; // unmark on the way back out — the whole point (see Pitfalls)
return false;
}
dfs(key(...start), 0, [key(...start)]);
return foundPath; // null if not found within this limit
}The outer loop is the "iterative deepening" part — plain, and identical in shape to the game-tree version's own outer loop:
function iddfs(grid, rows, cols, start, end) {
for (let limit = 0; limit <= rows * cols; limit++) {
const path = depthLimitedSearch(grid, rows, cols, start, end, limit);
if (path) return path; // first success is provably shortest
}
return null; // end unreachable
}Marking a cell visited for the whole iteration, instead of only while it's on the
current path, silently returns a wrong (too long) answer. Plain DFS marks a cell visited
forever once it's first reached, and reusing that habit here looks harmless — it even runs
faster, which makes it easy to miss. On this page's own demo maze the true shortest path
is 11 steps (confirmed against BFS). Swap the reference implementation's onPath[node] =
false unmark-on-backtrack for a plain "mark and never unmark" visited array, and depth-limited
search at limit 11 falsely reports the goal unreachable — some earlier, ultimately-failed branch
had already claimed a cell that the one real 11-step path needed, and a global visited flag has no
way to give that cell back once a different branch wants it. The algorithm doesn't fail loudly: it
keeps trying deeper limits and eventually reports 13, a real but non-shortest path, having done
less total work (135 node-visits versus the correct version's 188) to get the wrong answer.
The whole reason to reach for IDDFS over plain DFS is the shortest-path guarantee — a version that's
both faster and wrong defeats the point while looking, at a glance, like an optimization.
Checking the depth-limit cutoff before checking whether the current cell is the goal
gets the boundary case wrong. The reference implementation above tests node ===
endKey first and only checks the depth limit if that fails. Swap the order — cut off at the
limit before ever asking whether this cell is the goal — and a goal that sits exactly on the
current frontier (depth equal to the limit) gets treated as "out of reach" instead of "found," even
though the search is standing on it. On this page's own demo maze this doesn't crash or hang: it
just reports the shortest path as 12 steps instead of the true 11, because the iteration that
should have succeeded at limit 11 backs off one cell early, at a real extra cost of 244 total
node-visits instead of 188 to arrive at the wrong number.
IDDFS is not a strictly better BFS — it trades memory for extra time, and the trade can be steep. On this page's own demo maze, BFS reaches the same 11-step answer in 21 total node-visits; the correct IDDFS reference above takes 188 — a 8.95x overhead for an identical answer, all of it redundant shallow re-exploration. That ratio isn't fixed: it's driven by the graph's branching factor (see Why it works), so a bushier graph pays proportionally less and a narrow, corridor-like one pays proportionally more. Reach for IDDFS when the memory a full BFS frontier would need is the actual constraint — a huge or infinite implicit state space where storing one layer isn't feasible — not as a default drop-in replacement for BFS on a graph small enough to fit in memory outright.
Time: O(b^d) where b is the branching factor and
d the solution depth — dominated by the final, deepest iteration, with every shallower
iteration adding a bounded fraction on top (see Why it works). On this page's own grid maze, where
b stays small, that shows up as the measured 8.95x-over-BFS figure above rather than
a dramatic blowup; graphs or implicit search spaces with a larger branching factor pay a steeper
overhead in the same formula. Space: O(d) — only the single
root-to-current path needs to be held at once, the same bound as plain DFS and independent of how
large the reachable graph is, versus BFS's O(V) frontier in the worst case.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.