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 Inorder Traversal
Core idea: Recursion already does inorder for free — but the magic isn't the function calls, it's the stack those calls quietly maintain. If you build that stack yourself, you can do inorder traversal with an ordinary
whileloop. The whole algorithm is one sentence: go left as far as you can, pushing every node; then pop one, visit it, and step right — repeat.
Problem, rephrased
You're handed the root of a binary tree. Return its inorder traversal: the values visited in left subtree → node → right subtree order. The catch in this lesson: do it without recursion. You manage an explicit stack instead of leaning on the language's call stack.
Picture a museum audio-guide that walks an exhibit laid out as a binary tree of rooms. The rule: always finish the entire wing to your left before announcing the room you're standing in, and only then move right. A recursive guide would mentally "remember where it was" by stacking up unfinished rooms in its head — we're going to make that mental stack a real, physical stack of sticky notes so the guide can be paused and resumed mid-tour at any moment.
Consider this small tree:
Inorder means: drain the left subtree of 4 first (which itself means drain left of 2 first), visit, then go right.
| Step | Node visited | Why now |
|---|---|---|
| 1 | 1 |
leftmost — no left child remains |
| 2 | 2 |
1 (its left) is done |
| 3 | 3 |
2's right subtree |
| 4 | 4 |
entire left subtree of root drained |
| 5 | 6 |
root's right subtree, its left first... none |
| 6 | 7 |
6's right child |
Expected output: [1, 2, 3, 4, 6, 7]
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