Binary Tree Inorder Traversal Iterative: The curr and Stack Pattern
Learn iterative binary tree inorder traversal using a curr pointer and stack, with a full walkthrough, canonical JavaScript code, complexity, and pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Inorder traversal visits a binary tree in left, root, right order. That ordering is especially useful for binary search trees: it emits their values in ascending order. The iterative version is a classic interview test because it asks you to reproduce recursion's “come back to this parent later” behavior yourself.
The solution needs two pieces of state. curr walks down the current path, while a stack holds ancestors that cannot be visited yet because their left subtree still comes first. Go left until you cannot; then pop, record, and move right.
The problem
Given a binary tree root, return its values in inorder order: traverse the full left subtree, visit the node, then traverse its right subtree. For the level-order input 1,null,2,3:
1
\
2
/
3
Output: [1, 3, 2]The order is not based on numeric value. It is structural. The sorted-output property only applies when the given tree actually satisfies the binary-search-tree ordering rule.
The recursive baseline
Recursion expresses inorder in three lines:
function inorder(root, ans = []) {
if (!root) return ans;
inorder(root.left, ans);
ans.push(root.val);
inorder(root.right, ans);
return ans;
}Before a recursive call descends left, the runtime remembers the current node and its unfinished right subtree in a call frame. When the left call returns, that frame resumes, records the node, and starts the right call. Iteration must preserve exactly that postponed work. A stack of nodes is the explicit form of those frames.
The key insight: descend first, then unwind
Never record a node when you first encounter it: its left subtree has not been handled. Instead, push every node while moving curr left. The top stack entry is always the deepest ancestor whose left side has been completely explored but whose own value is still waiting.
When curr becomes null, pop that waiting node and record it. Its right child becomes the new curr, and the same left descent repeats. The outer loop must continue while either curr exists or the stack has saved ancestors. Using && would stop too early whenever a left descent reaches null with nodes waiting to be popped.
The optimal iterative solution
This is the visualizer's canonical JavaScript solution. It does not need a special empty-tree return: with root null and an empty stack, the outer condition is false and ans is returned.
var inorderTraversal = function (root) {
let ans = [];
let stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.push(curr.val);
curr = curr.right;
}
return ans;
};The inner loop performs the “left” part of left-root-right. The three statements after it perform “root, then right.” Assigning the popped node back to curr is convenient: it gives the code one variable for the node being recorded and then for its right subtree.
Walkthrough: why the stack is necessary
Use the full tree 4,2,6,1,3,5,7. The stack is shown from bottom to top, with the rightmost entry popped next.
| Step | curr / action | Stack after action | Result |
|---|---|---|---|
| Start | curr = 4 | [] | [] |
| 1 | push 4, go left to 2 | [4] | [] |
| 2 | push 2, go left to 1 | [4, 2] | [] |
| 3 | push 1, go left to null | [4, 2, 1] | [] |
| 4 | pop and record 1; move right null | [4, 2] | [1] |
| 5 | pop and record 2; move right to 3 | [4] | [1, 2] |
| 6 | push 3, go left null; pop and record 3 | [4] | [1, 2, 3] |
| 7 | pop and record 4; move right to 6 | [] | [1, 2, 3, 4] |
| 8 | repeat on 6 and its children | [] | [1, 2, 3, 4, 5, 6, 7] |
At step 3, node 4 is still on the stack even though curr reached null. That is why the condition is curr || stack.length: a null current pointer means “finished this left branch,” not “finished the tree.”
Complexity
| Approach | Time | Extra space | Why |
|---|---|---|---|
| Recursive inorder | O(n) | O(h) | Each node gets one call; active path has height h |
| Iterative inorder | O(n) | O(h), O(n) worst case | Every node is pushed once and popped once |
| Morris traversal | O(n) | O(1) | Reuses temporary tree links, which is more invasive |
The stack contains a root-to-current path and postponed ancestors. In a balanced tree that is O(log n); in a skewed tree it reaches O(n). Iteration keeps that storage out of the language call stack.
Common mistakes
- Record while pushing left. That is preorder behavior; inorder must finish the left subtree first.
- Use
while (curr && stack.length). If either is empty, the traversal may still have work. The correct outer condition is an OR. - Forget
curr = curr.rightafter recording. You will never explore the popped node's right subtree. - Pop before the inner left loop finishes. The popped node must be the leftmost unprocessed node, not merely the first node encountered.
- Claim every inorder result is sorted. Only a valid BST has that property; an arbitrary binary tree need not.
Where this pattern shows up next
Traversal order is a tool for a particular question, not just a memorization exercise:
- Binary Tree Preorder Traversal records before exploring children.
- Binary Tree Inorder Traversal introduces the same left-root-right order.
- Binary Tree Preorder Traversal - Iterative shows the simpler pop-record-push stack shape.
Postorder is the complementary challenge: it delays recording until both subtrees are complete, so an iterative version needs extra state or an additional stack.
You can step through it interactively and watch ancestors wait on the stack until their left subtree is done.
FAQ
Why does iterative inorder use both curr and a stack?
curr follows the subtree currently being explored. The stack stores ancestors that cannot be visited yet because inorder requires their left subtree first. Together they reproduce recursive call frames without recursive calls.
Why is inorder traversal sorted for a BST?
In a binary search tree, every left-subtree value is smaller than its node and every right-subtree value is larger. Visiting left, then node, then right therefore emits values in ascending order. Duplicates depend on the BST's chosen duplicate policy.
What is the iterative inorder base case for a null root?
No separate branch is required in this implementation. curr is null and stack.length is zero, so the outer loop never starts and the initialized empty answer array is returned.
Can I use recursion instead of a stack?
Yes, and recursion is often clearer. Use the iterative pattern when the prompt requires it, when tree depth may exceed the runtime's call-stack limit, or when explicit traversal state is useful.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.