BFS, DFS, UCS & IDDFS

You’re back at the start of that maze. The four algorithms in this lesson are uninformed — they have no map, no compass, no sense of which doorway “feels” closer to the exit. All they can do is pick the next node by the structure of what they’ve seen so far. Surprisingly, that’s enough to solve a huge family of problems.

The trade-off is the whole story. Some are complete (guaranteed to find a solution if one exists) but eat memory. Some are tiny on memory but get stuck on infinite branches. One — IDDFS — sounds wasteful at first glance 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’re visiting 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 costs the same). Not necessarily if costs vary.
• Time? O(b^d) — must look at most 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 until a dead end, then backtracks.

• Complete? No on infinite trees — DFS can dive forever down an infinite branch and never come back. On finite trees with a visited set, yes.
• Optimal? No — the first goal found is whichever branch DFS chose, not the shortest.
• Time? O(b^m) in the worst case, where m is the maximum tree depth. If m is much bigger than d, DFS can be much 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 edge costs aren’t all the same? 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. 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*/eps)) where C* is the optimal cost and eps is 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’s the clever one. Run DFS with depth limit 1. If no goal, restart from scratch and run DFS 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 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. This is why it’s the standard uninformed search for large state spaces — the same memory-vs-completeness trade-off 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 starting from A?” — count or list. Both 2024 and 2026 included a question on IDDFS or DFS-properties; GATE DA 2024 explicitly asked the worst-case root-expansion count for IDDFS.

Worked example

From the 2024 sample paper. 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’s d + 1 iterations, so the root is re-expanded d + 1 times. (Many treatments round this to “about d times” or simply “O(d)” — both are accepted. IDA* re-expansion behaves analogously, with the root touched once per f-limit iteration.)

Why doesn’t this 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 at 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? Answer: 2, because the children of A can be queued in either order (B, C or C, B), and each child has only one descendant — so the two valid orders are A, B, C, D, E and A, C, B, E, D.

Quick check