Skip to content
CCC Python Course

Iterative DFS and recursion elimination

Stage
5
Module
M5.7
Lessons
1

In this module

  • Implement depth-first search using an explicit stack instead of recursion.
  • Use preorder and postorder (reverse-preorder) processing in iterative DFS.
  • Maintain per-node iterator indices for true DFS-tree properties.
  • Apply iterative DFS to avoid recursion depth limits on large graphs.

Before this module

M4.13BFS and flood fill (iterative)M1.14Recursion fundamentals

Lessons

  1. 1Iterative DFS and recursion elimination

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2016 S3
    Phonomenal Reviews (opens on DMOJ in a new tab) DMOJ

    Mark subtrees for removal and count edges carefully to minimize the total length.

    Why DMOJ: An older tree problem, solvable with an iterative DFS, that still makes good practice for this module.

  2. 2024 S4
    Painting Roads (opens on WMOJ in a new tab) WMOJ

    Colour the nodes of a DFS tree using the parity of each node's depth.