Iterative Traversal
What is this?
Normally you walk a tree by writing a function that calls itself (recursion), and the computer quietly keeps track of where you are. Here you do that bookkeeping yourself using a simple to-do list called a stack — a pile where you always grab the most recently added item first. The payoff: you can pause the walk halfway, resume it later, and handle trees so deep that recursion would crash.
💡 Fun fact: Recursion is never magic — behind the scenes the computer uses its own hidden stack. Doing it by hand is exactly what's happening under the hood, just made visible.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Every recursive tree walk is secretly using a stack — the call stack. Make that stack explicit and you can traverse a tree without recursion: useful when the depth could overflow the call stack, or when you need to pause and resume the walk (an iterator). The three orders differ only in when you visit a node relative to pushing its children.
The three orders, one machine
All three carry a stack and process O(n) nodes once, in O(n) time and O(h) space (the stack holds at most one root-to-leaf path). What changes is the bookkeeping that places the "visit" at the right moment.
The three problems
- Iterative Preorder — the gentlest: push root, pop-visit, push right child then left so left comes off first.
- Iterative Inorder — push the entire left spine, pop and visit, then step right and repeat; BST inorder yields sorted order.
- Iterative Postorder — hardest recursively; the trick is to do a modified preorder
(Node, Right, Left)and reverse the result.
Key takeaways
- The explicit stack is the call stack, externalized — same pushes and pops, done by hand.
- Preorder visits on pop; inorder visits after the left spine; postorder is reverse of (Node, Right, Left).
- O(n) time, O(h) space for all three.
- Why it matters: controlling the stack lets you bound depth and build pausable iterators (see BST Iterator).
Order: Iterative Inorder → Iterative Preorder → Iterative Postorder.