Binary Tree Preorder Traversal Iterative: Master the Stack
Learn binary tree preorder traversal iteratively with a stack, including the right-before-left rule, a traced example, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Preorder traversal visits a tree in root, left, right order. The recursive version is compact because the language call stack remembers where to return after each child. The iterative version has to make that memory visible: use an array as a stack.
That sounds like a mechanical translation, but one ordering choice decides whether the result is preorder or subtly wrong. You push the right child before the left child. A stack is last-in, first-out, so the left child is then the next node removed and visited.
The problem
Given the root of a binary tree, return the values in preorder: visit the current node, then its left subtree, then its right subtree. A level-order representation such as 1,null,2,3 describes this tree:
1
\
2
/
3
Output: [1, 2, 3]An empty tree should return []. Values may repeat, so traversal must follow node references rather than treating values as unique identifiers.
The recursive baseline
The direct recursive definition mirrors the traversal rule exactly:
function preorder(root, ans = []) {
if (!root) return ans;
ans.push(root.val);
preorder(root.left, ans);
preorder(root.right, ans);
return ans;
}This is a fine solution when recursion is allowed. Its limitation is not time: every node is still visited once. It is that a very deep, skewed tree creates one call frame per node. JavaScript engines have a finite call-stack limit, so a long chain can throw before the traversal finishes. An explicit stack stores the same deferred work on the heap and makes the visit order easy to inspect or animate.
The key insight: reverse the sibling push order
When a node is popped, preorder records it immediately. Its children must be scheduled so that the left child runs first. Because a stack pops the most recently pushed item, scheduling left then right would visit right first. Push right, then left instead.
Think of the stack as a to-do list whose top is next. After processing node 1, putting 3 on the list and then 2 on top gives the desired next task: visit 2. The right subtree remains saved until the left subtree is complete.
This is iterative depth-first search. The tree has no cycles, so nodes do not need a visited set; each child reference is scheduled exactly once by its parent.
The optimal iterative solution
This is the visualizer's canonical JavaScript algorithm. curr?.val is safe here because the stack contains nodes, while optional chaining keeps the expression harmless if that assumption ever changes.
var preorderTraversal = function (root) {
if (!root) return [];
let ans = [];
let stack = [root];
while (stack.length) {
let curr = stack.pop();
ans.push(curr?.val);
curr?.right && stack.push(curr?.right);
curr?.left && stack.push(curr?.left);
}
return ans;
};The initial root push gives the loop a first node to process. Each iteration removes one pending node, records it, and adds its children if they exist. The loop ends precisely when no node remains pending. Notice that recording comes before either child is pushed or processed: that is the “root” part of root-left-right.
Walkthrough: a tree with both subtrees
Trace 1,2,3,4,5,6,7, a full tree. The stack below is written bottom to top, so the final entry is popped next.
| Step | Pop / action | Stack after action | Result |
|---|---|---|---|
| Start | push root 1 | [1] | [] |
| 1 | pop 1, record it; push 3, then 2 | [3, 2] | [1] |
| 2 | pop 2, record it; push 5, then 4 | [3, 5, 4] | [1, 2] |
| 3 | pop 4, record it; no children | [3, 5] | [1, 2, 4] |
| 4 | pop 5, record it; no children | [3] | [1, 2, 4, 5] |
| 5 | pop 3, record it; push 7, then 6 | [7, 6] | [1, 2, 4, 5, 3] |
| 6-7 | pop 6, then 7 | [] | [1, 2, 4, 5, 3, 6, 7] |
The moment after step 1 is the crucial proof. Although 3 was pushed first, 2 sits on top and is popped first. Reversing those two pushes would produce root-right-left traversal instead.
Complexity
| Approach | Time | Extra space | Why |
|---|---|---|---|
| Recursive preorder | O(n) | O(h) | One call per node; up to tree height h frames |
| Iterative preorder | O(n) | O(h), O(n) worst case | Each node is pushed and popped once; pending branches occupy the stack |
| Breadth-first traversal | O(n) | O(w) | A queue holds a level, but it returns a different order |
For a balanced tree, height is O(log n), though the explicit stack can temporarily hold deferred right branches. In the worst shape, O(n) storage is possible. The iteration still avoids the language call-stack limit.
Common mistakes
- Push left before right. That makes the right child sit on top, producing root-right-left order.
- Record after scheduling children. Scheduling is not visiting, but muddling these phases often leads to an inorder or postorder implementation.
- Start with an empty stack without handling
null. Pushing a null root forces extra checks. Return[]before creating[root]. - Use
shift()as the work-list operation. It turns this into queue-like behavior and is O(n) per removal for normal JavaScript arrays. - Assume preorder values are sorted. Traversal order reflects tree shape. Only inorder traversal of a binary search tree is sorted.
Where this pattern shows up next
The same explicit-work-list idea appears in several tree problems, even when the output changes. Zigzag level order switches to level-oriented processing and alternates direction. Right-side view keeps the last visible node at each depth. Maximum-depth variants carry depth as traversal state. In each case, ask what work must wait and choose the data structure whose removal order matches that work.
You can step through it interactively to see the stack enforce left-before-right at every node.
Try a tree with a missing child as well as a full tree. Seeing an absent child cause no push makes the loop invariant concrete: the stack contains only real nodes that remain to be visited.
FAQ
Why does iterative preorder push the right child first?
A stack is last-in, first-out. Pushing right first and left second places left on top, so the next pop visits the left subtree. This recreates preorder's root-left-right rule without recursion.
Is iterative preorder better than recursive preorder?
Both take O(n) time and are equally valid for ordinary trees. Iteration is useful when tree depth can be large, when an environment limits recursion depth, or when you want direct control over pending nodes.
What happens for an empty binary tree?
The function returns an empty array immediately. This avoids putting null in the stack and ensures the loop only handles actual tree nodes.
Does preorder traversal use a queue or a stack?
It uses a stack for depth-first traversal. A queue processes nodes in first-in, first-out order and produces breadth-first, or level-order, traversal instead.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.