BFS, DFS, UCS & IDDFS

Last lesson laid the puzzle out as a search tree and left the real question hanging: in what order do you walk it? The four algorithms here all answer that, and they all answer it blind — uninformed, meaning no map, no compass, no sense of which doorway “feels” closer to the exit. All any of them can do is pick the next node from the structure of what it has already seen. Surprisingly, that is enough to crack a huge family of problems.

The trade-off is the whole story, judged on four counts: is the strategy complete (guaranteed to find a solution if one exists), is it optimal (does it find the cheapest), and what does it cost in time and space? Some are complete but devour memory. Some sip memory but get lost down infinite branches. And one — IDDFS — sounds wasteful at first and turns out to be the best of both.

A live picker — step through a small graph

Watch BFS spread in rings while DFS plunges down a branch. They visit the same graph; only the order differs.

BFS — Breadth-First Search

BFS uses a FIFO queue: enqueue the start, then repeatedly pop the front and enqueue its unvisited successors. Every node at depth d is reached before any node at depth d + 1.

• Complete? Yes — if a solution exists at any finite depth, BFS finds it.
• Optimal? Yes for unit step costs (every edge the same). Not necessarily when costs vary.
• Time? O(b^d) — it may look at every node up to depth d.
• Space? O(b^d) — the frontier holds an entire level. This is BFS’s pain point.

DFS — Depth-First Search

DFS uses a LIFO stack (or recursion). It commits to one branch and walks down to a dead end, then backtracks.

• Complete? No on infinite trees — DFS can dive forever down one infinite branch and never come back. On finite trees with a visited set, yes.
• Optimal? No — the first goal found is whichever branch DFS happened down, not the shortest.
• Time? O(b^m) worst case, where m is the maximum tree depth. If m is much bigger than d, DFS can be far slower than BFS.
• Space? O(b · m) — only the current path and its siblings sit on the stack. This is DFS’s superpower.

UCS — Uniform-Cost Search

What if the edge costs are not all equal? BFS is no longer optimal. Uniform-Cost Search is BFS upgraded to a priority queue keyed on g(n) — the total path cost from the start to node n — so it always expands the cheapest node next.

• Complete? Yes if step costs have a positive lower bound (no zero-cost loops).
• Optimal? Yes for non-negative edge weights — by the time it pops a node, it has found the cheapest path to it.
• Time/Space? Roughly O(b^(1+C*/ε)) where C* is the optimal cost and ε the smallest edge cost. Bad in pathological cases; in practice close to BFS.

UCS is the uninformed analogue of Dijkstra’s algorithm.

IDDFS — Iterative Deepening DFS

Here is the clever one. Run DFS with depth limit 1; if no goal, restart from scratch with depth limit 2; then 3, then 4, until you hit a depth where DFS finds the goal. It sounds wasteful — you redo the shallow levels every time — but look at the counts.

• Complete? Yes — same as BFS, every finite depth gets reached.
• Optimal? Yes for unit step costs (same as BFS).
• Time? O(b^d) — the leaves dominate; the wasted re-expansions of shallow levels add only a constant factor.
• Space? O(b · d) — only one DFS path sits on the stack at a time.

IDDFS wins on memory while keeping completeness, which is why it is the standard uninformed search for large state spaces — the same memory-vs-completeness trade-off that decides which traversal a graph database, a build-dependency resolver, or a puzzle solver reaches for in practice.

How GATE asks this

Two recurring shapes. MCQ: “Which of the following are uninformed search strategies?” — the answer is BFS, DFS, UCS, IDDFS (and depth-limited DFS); A*, greedy best-first, and hill-climbing are informed. NAT: “On the following graph, in what order does BFS visit nodes from A?” — count or list. Both 2024 and 2026 ran a DFS/IDDFS-properties question; GATE DA 2024 explicitly asked the worst-case root-expansion count for IDDFS.

Worked example — GATE DA 2024

In the worst case, how many times does iterative-deepening DFS (IDDFS) re-expand the root node, on a tree with branching factor b and goal at depth d?

The root is expanded once per iteration: iteration 0 (depth-limit 0), iteration 1, …, iteration d. That is d + 1 iterations, so the root is re-expanded d + 1 times. (Many treatments round this to “about d times” or simply O(d).)

Why does this not make IDDFS slow? Total work is

  1·(d+1) + b·d + b^2·(d-1) + ... + b^d·1   ≈   b^d · (constant)

— the leaves at depth d outweigh everything above them, so the total stays O(b^d), the same order as BFS, while space stays O(bd).

A second 2024-style question. Given the small graph

     A
    / \
   B   C
   |   |
   D   E

with neighbour lists A: [B, C], B: [D], C: [E], how many distinct BFS orders are possible from A? The answer is 2: the children of A can be queued in either order (B, C or C, B), and each child has a single descendant — so the two valid orders are A, B, C, D, E and A, C, B, E, D.

In one breath

The four uninformed strategies order the tree-walk by structure alone: BFS (FIFO queue) is complete and optimal under unit costs but pays O(b^d) space; DFS (LIFO stack) is cheap at O(bm) space but incomplete on infinite trees and non-optimal; UCS (priority queue on path cost g(n)) is the Dijkstra-like one, optimal for any non-negative weights; and IDDFS restarts DFS at growing depth limits, re-expanding the root d+1 times yet keeping DFS’s O(bd) space and BFS’s completeness, because the b^d leaves dominate so its time is still O(b^d).

Practice

A question to carry forward

Every strategy here shared one blindfold: none had the faintest idea which doorway led toward the exit. BFS fanned out in all directions equally; DFS guessed a corridor and committed; UCS followed the cheapest crumbs so far — but not one of them could look ahead. So on a big maze they all thrash through vast regions that lead nowhere near the goal.

Yet a person standing in a maze can often see the exit over the hedges and simply head that way. What if you could whisper to the search, at every node, a rough “you’re about this far from the goal”? Even an imperfect estimate would let it ignore the doors pointing the wrong way and chase the promising ones. Here is the thread onward: what exactly is that estimate, what single honesty rule must it obey so the search still returns the cheapest path and not just a path — and what is the difference between merely never lying and obeying a stricter triangle inequality?