Iterative Preorder with Stack
What you'll learn: You'll discover how to convert a recursive preorder traversal into an iterative version using an explicit stack.
The Core Idea
Remember that recursive preorder traversal visits nodes in Root-Left-Right order, relying on the call stack to remember where to go next. We can mimic this behavior manually using our own stack data structure.
The algorithm works like this:
- Push the root onto the stack
- While the stack isn't empty:
- Pop a node and process it (visit it)
- Push the right child (if it exists)
- Push the left child (if it exists)
Why Right Before Left?
This is the clever part! Since a stack is Last-In-First-Out (LIFO), we push the right child first so it waits deeper in the stack. Then we push the left child on top. When we pop next, we get the left child—which is exactly what preorder wants (visit left before right).
Think of it like stacking plates: the last plate you put on top is the first one you take off.
Visual Example
For a tree with root A, left child B, and right child C:
- Push
A→ Stack:[A] - Pop
A, process it, pushC, then pushB→ Stack:[C, B] - Pop
B, process it (B's children would be pushed if any) - Pop
C, process it
Result: A, B, C — perfect preorder!
Why Use This?
Sometimes recursion isn't practical (deep trees might overflow the call stack, or you're in an environment that limits recursion). The iterative approach gives you explicit control and can be more efficient.
Key Takeaway: Iterative preorder uses an explicit stack: push root, then repeatedly pop-process-push right-push left to achieve Root-Left-Right order without recursion.