IDDFS is optimal, meaning that it finds the shallowest goal.

, the cumulative order in which nodes are first visited is effectively the same as in breadth-first search.

[1] The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS) for directed graphs.

If the goal node is found by DLS, IDDFS will return it without looking deeper.

Otherwise, if at least one node exists at that level of depth, the remaining flag will let IDDFS continue.

2-tuples are useful as return value to signal IDDFS to continue deepening or stop, in case tree depth and goal membership are unknown a priori.

Another solution could use sentinel values instead to represent not found or remaining level results.

[2] Iterative deepening visits states multiple times, and it may seem wasteful.

, the cost of repeatedly visiting the states above this depth is always small.

This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as

This can be phrased as each depth of the search corecursively producing a better approximation of the solution, though the work done at each step is recursive.

This is not possible with a traditional depth-first search, which does not produce intermediate results.

The time complexity of IDDFS in a (well-balanced) tree works out to be the same as breadth-first search, i.e.

[1]: 5  So the total number of expansions in an iterative deepening search is where

(i.e., if the branching factor is greater than 1), the running time of the depth-first iterative deepening search is

more nodes than a single breadth-first or depth-limited search to depth

[4] The higher the branching factor, the lower the overhead of repeatedly expanded states,[1]: 6  but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadth-first search.

Since IDDFS, at any point, is engaged in a depth-first search, it need only store a stack of nodes which represents the branch of the tree it is expanding.

Since it finds a solution of optimal length, the maximum depth of this stack is

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.

forever, caught in the A, B, D, F, E cycle and never reaching C or G. Iterative deepening prevents this loop and will reach the following nodes on the following depths, assuming it proceeds left-to-right as above: (Iterative deepening has now seen C, when a conventional depth-first search did not.)

For this graph, as more depth is added, the two cycles "ABFE" and "AEFB" will simply get longer before the algorithm gives up and tries another branch.

Otherwise, the search depth is incremented and the same computation takes place.

One limitation of the algorithm is that the shortest path consisting of an odd number of arcs will not be detected.

When the depth will reach two hops along the arcs, the forward search will proceed from

Pictorially, the search frontiers will go through each other, and instead a suboptimal path consisting of an even number of arcs will be returned.

This is illustrated in the below diagrams: What comes to space complexity, the algorithm colors the deepest nodes in the forward search process in order to detect existence of the middle node where the two search processes meet.

Additional difficulty of applying bidirectional IDDFS is that if the source and the target nodes are in different strongly connected components, say,

The running time of bidirectional IDDFS is given by and the space complexity is given by where

Since the running time complexity of iterative deepening depth-first search is