Iterative Inorder Traversal of Binary Tree
EasyDescend left, pop, then go right
Problem
Return the inorder traversal of a binary tree iteratively using a stack.
Push all left nodes, pop and output, then move to the right child.
The idea
Push nodes while walking as far left as possible; when you can go no further, pop and record that node, then move to its right child and repeat. The stack holds exactly the ancestors you still owe a visit.
The trick
- Only record on the pop, never on the push.
- The loop continues while the stack is non-empty or the current node is not null.
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, 3, 2]
- Explanation:
- Left, node, right → 1,3,2.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [2, 1, 3]
- Explanation:
- Gives 2,1,3.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty → 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.