Binary Tree Inorder Traversal
Return a binary tree's values in inorder (left subtree, node, right subtree), iteratively with an explicit stack instead of recursion.
Problem Understanding
Binary Tree Inorder Traversal: given the root of a binary tree, return the inorder traversal of its values: left subtree, then the node, then the right subtree.
Examples: [1,null,2,3] → [1,3,2]; [1,2,3,4,5,null,8,null,null,6,7,9] → [4,2,6,5,7,1,3,9,8]; [] → [].
The Intuition: The Stack Is the Call Stack
Recursion makes inorder trivial; doing it with a loop means simulating what the call stack remembers:
- Go left as far as possible, pushing each node: none of them can be recorded until its left side is done.
- Pop when you run out of left children: that node's left side is finished, so record it.
- Move to its right child and repeat from step 1.
It is one of the three DFS tree traversals, and the same loop drives Kth Smallest Element in a BST, which just stops early.
Interactive Walkthrough
OUTLINED = ON THE STACK · #n = n-TH IN THE OUTPUT
START AT ROOT
stack size
0
recorded
0
stack (top last)
Empty
result
None yet
Start at the root 1 with an empty stack
Next
Push 1 and go left to 2
root
Legend & Complexity
The node just pushed or popped
On the stack: ancestors whose left side is still being walked
Recorded, numbered in output order
Time
O(n)
Space
O(h)
Nodes on the stack are outlined and linked, so the stack reads as a path of waiting ancestors. Each recorded node turns green with its position in the output. Try BST to see sorted output.
Dry Run Table
Input: [1,null,2,3] (1's right child is 2; 2's left child is 3).
| Step | Stack | Result |
|---|---|---|
| push 1 | [1] | [] |
| pop 1, go right to 2 | [] | [1] |
| push 2, push 3 | [2, 3] | [1] |
| pop 3 | [2] | [1, 3] |
| pop 2 | [] | [1, 3, 2] |
Answer: [1,3,2].
The Solution Template
The iterative loop; the C version assumes LeetCode's limit of 100 nodes.
Binary Tree Inorder Traversal Code
1var inorderTraversal = function(root) {2 const result = [], stack = [];3 let node = root;4 while (node || stack.length) {5 while (node) {6 stack.push(node);7 node = node.left;8 }9 node = stack.pop();10 result.push(node.val);11 node = node.right;12 }13 return result;14};
Edge Cases & Common Mistakes
- Empty tree: the loop never runs; return
[]. - Loop condition: continue while there is a node or the stack is non-empty, or the walk stops after the first right turn.
- Recording on push: that gives preorder, not inorder.
- Skewed trees: the stack can hold all n nodes (h = n).
- Deep recursion: the iterative version avoids stack-overflow on very deep trees.
Summary
Push nodes going left; when you cannot go left, pop, record, and move right. Repeat until there is no node and the stack is empty. O(n) time, O(h) space.
More practice: DSA interview questions with answers · patterns cheat sheet