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.
Iterative Preorder Traversal
Core idea: Preorder visits each node before its children, in the order node → left subtree → right subtree. The recursive version leans on the call stack to remember "after I finish a node, go left, then go right." To kill the recursion, make that stack explicit: push the root, then loop — pop a node, visit it immediately, and push its children back so the left child comes off the stack next. A stack is last-in-first-out, so to process left before right you must push right first, then left. That single inversion is the whole trick. The result is an
O(n)time,O(h)space traversal that never recurses.
The problem, rephrased
You're handed the root of a binary tree. Walk it in preorder — for every node, record the node's own value first, then everything in its left subtree, then everything in its right subtree — and return the list of values. The catch: do it without recursion. No helper that calls itself; you manage your own stack.
This is LeetCode 144 — Binary Tree Preorder Traversal.
Consider this small tree:
Preorder says: visit 1, then dive into the whole left subtree of 1 (rooted at 2), then the whole right subtree (rooted at 3). Recursing into 2: visit 2, then its left (4), then its right (5). Then back up to the right side: visit 3, then its left (nothing), then its right (6).
| Step | Node visited | Why now |
|---|---|---|
| 1 | 1 |
root, visited before its children |
| 2 | 2 |
left subtree of 1, root-first |
| 3 | 4 |
left child of 2 |
| 4 | 5 |
right child of 2 |
| 5 | 3 |
right subtree of 1, root-first |
| 6 | 6 |
right child of 3 |
Expected preorder: [1, 2, 4, 5, 3, 6].
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson