CoreSource checked

Iterative Deepening DFS

Runs depth-first search repeatedly with increasing depth limits.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Depth-Limited Search
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: IDDFS

Overview

Iterative Deepening DFS combines the low memory use of DFS with the level-by-level discovery behavior of BFS.

Core Concepts

graph representationtraversal orderrecursive decompositioncandidate searchdepth-limited searchvisited setfrontier expansion

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(b^d)

Average

O(b^d)

Worst

O(b^d)

Space

O(d)

When to Use

Use Iterative Deepening DFS when you need to search to a limited depth.
Use it for game tree search with inputs like graph or state space.
Use it when relationships are naturally modeled as nodes connected by edges.
Use it when the Depth-Limited Search tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when recursion depth can exceed the runtime stack limit.
Avoid it when the graph is so large that storing every visited node is not practical.
Avoid it when O(b^d) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not found node or no-result.

What It Does

Searches to a limited depth
Repeats with deeper limits until a target is found

Use Cases

Game tree search
Memory-limited graph search
Unknown-depth target search

Inputs

Graph or state space
Start node
Target test

Outputs

Found node or no-result
Search depth

Pseudocode

1.Start with depth limit zero
2.Run depth-limited DFS
3.Return if the target is found
4.Increase the depth limit
5.Repeat until a maximum limit is reached

Canonical Example

Input: graph = {A: [B, C], B: [D], C: [], D: []}, start = A
Output: visited = [A, B, C, D]
Explanation: Iterative Deepening DFS: The traversal starts at A and visits reachable nodes by following edges.

Implementation Notes

Keep the input contract explicit: Graph or state space; Start node; Target test.
Use this step as the implementation spine: Start with depth limit zero.
Then preserve the next state change: Run depth-limited DFS.
Keep node ids, edge direction, and visited state explicit in the implementation.
Represent neighbors consistently and keep traversal state separate from the graph data.

Common Pitfalls

The repeated shallow work is often acceptable when branching grows quickly.
Not defining directed versus undirected edges clearly can change the result.
Forgetting to mark visited nodes before revisiting cycles or shared neighbors.
Returning found node or no-result without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the same tree searched again with deeper limits.

Step 1 of 5: Start with depth limit zero

deepening-tree

Notes

Iterative Deepening DFS operates in O(b^d) time and O(d) space within the Depth-Limited Search family. Often compared with Depth-First Search and Breadth-First Search.