Iterative Preorder Traversal of Binary Tree
EasyA stack, right child pushed first
Problem
Return the preorder traversal of a binary tree using a stack (no recursion).
Use an explicit stack: pop a node, output it, push right then left.
The idea
Pop a node, record it, then push its right child before its left so the left is processed next. Pushing in reverse is what makes a LIFO stack produce a left-to-right order.
The trick
- Push right, then left — the stack reverses them.
- O(n) time, O(height) space, with no recursion.
Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.
1/8
Optimal
timeO(n)spaceO(h)
Order = when you emit the node.
1function inorder(node) {2 if (!node) return;3 inorder(node.left);4 visit(node.val); // node between children5 inorder(node.right);6}Input
- nodes
- 6, 5 edges
Output
- output
- —
- inorder
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,null,2,3]
- Output:
- [1, 2, 3]
- Explanation:
- Root, then left subtree, then right → 1,2,3.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [1, 2, 3]
- Explanation:
- Visit 1, then 2, then 3.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty tree → nothing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.