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 Postorder Traversal
Core idea: Postorder visits Left → Right → Node — a node only after both its subtrees are done. The cleanest iterative trick is to run a modified preorder (Node → Right → Left) with a stack and reverse the result, because postorder is exactly that sequence read backwards.
Problem, rephrased
You're handed the root of a binary tree. Walk it in postorder — Left → Right → Root — and return the values in visit order. The catch: do it without recursion (LeetCode 145).
Forget abstract nodes for a moment. Imagine you're tearing down a cloud deployment. Each service node depends on the services beneath it, so you can only safely shut down (or bill, or aggregate) a parent after every child below it is already finished. You drain the leaves first and work upward; the root — the thing everyone depends on — goes last. That "children fully done before the parent" rule is postorder.
Here's a small tree to anchor every example below:
| Input (tree) | Postorder output (Left, Right, Node) |
|---|---|
| the tree above | [4, 5, 2, 6, 3, 1] |
empty tree (root = None) |
[] |
single node [42] |
[42] |
Notice the root 1 is last, and within each subtree the parent trails its children: 4, 5 come before their parent 2; 6 comes before 3.
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