Iterative traversal with a stack
Push the left spine; pop, visit, then push the right child's left spine.
The stack holds the ancestors whose left side is done but who are not yet visited.
01The intuition
Start with what you would do by hand
A binary search tree keeps smaller values to the left and larger values to the right. Walking it in the order "left side, me, right side", the inorder, lists the values from smallest to largest. The recursive version is three lines. But sometimes you cannot use recursion: a tree a million nodes deep would blow the call stack, or the problem wants an iterator object with a next() method that returns one value at a time and pauses in between. Recursion cannot pause.
Take the tree: 4 at the top; 2 and 6 below; 1 and 3 under 2; 7 under 6. By hand you walk down to the far left, say 1, then step back to 2, then look right (3), step back to 4, and so on. The "step back" is the part a plain loop cannot do, because a node does not know its parent. We need our own memory of the way we came.
Build the structure, one piece at a time
Piece one: a stack. A pile where you add on top and remove from the top. Two operations: push and pop. It will hold the nodes we walked through on the way down, so we can step back to them.
Piece two: the left spine. From the current node, keep going to the left child, pushing each node as you pass. Stop when there is no left child. The stack now holds the path from where you started down to the leftmost node, with the leftmost on top.
Piece three: pop, visit, go right. Pop the top node: it has no unvisited left side, so it is next in order. Output it. Then move to its right child and run piece two from there. If there is no right child, just pop again.
| Action | Stack (bottom → top) | Output so far |
|---|---|---|
| push the left spine from 4 | 4, 2, 1 | |
| pop 1, visit, right is empty | 4, 2 | 1 |
| pop 2, visit, go right to 3, push spine | 4, 3 | 1, 2 |
| pop 3, visit, right is empty | 4 | 1, 2, 3 |
| pop 4, visit, go right to 6, push spine | 6 | 1, 2, 3, 4 |
| pop 6, visit, go right to 7, push spine | 7 | 1, 2, 3, 4, 6 |
| pop 7, visit, right is empty | (empty) | 1, 2, 3, 4, 6, 7 |
Stop when the stack is empty and there is no node to walk from. For an iterator, next() is exactly one "pop, visit, push the right child's spine", and hasNext() is "the stack is not empty".
Why it is correct
The invariant: the stack holds exactly the nodes whose left side has been fully handled but who have not been output yet, in order from top of tree to bottom. Pushing a left spine keeps it true: every node pushed is waiting on its left side, and the spine ends where there is no left side. Popping the top keeps it true: the top is the deepest waiting node, nothing on its left remains, so it is the smallest unvisited value and the correct next output. Walking into its right child and pushing that spine is the same situation one level down.
next output = the top of the stack, which is the smallest value not yet output
Why it is fast
Each node is pushed exactly once and popped exactly once, so a full traversal is 2n stack operations, O(n). A single next() call can push a long spine, but across all calls the pushes total n, so next() is O(1) on average. The stack never holds more than one root-to-leaf path, so memory is O(h), the height, which is much less than n for a balanced tree.
How to recognise it in an interview
"Without recursion", "implement an iterator over a BST", "kth smallest", "next and hasNext in O(1) average and O(h) memory". Say: "I will keep an explicit stack of the left spine; pop gives the next value and I then push the right child's left spine." Binary Search Tree Iterator is exactly this object. Kth Smallest Element in a BST runs the same loop and stops after k pops. Validate Binary Search Tree uses the loop and checks that each popped value is larger than the previous one.
02The idea in one line
Push the left spine; pop, visit, then push the right child's left spine.
Reach for it when: Inorder iterator, BST iterator, kth smallest, flatten, Morris traversal.
Cost: O(n) time, O(h) space.
03The walk-through, step by step
The video works one example: Inorder of [1,null,2,3] iteratively. These are its captions in order, so you can follow without the video or check a step you missed.
- Walk left as far as possible, pushing every node
- Push 4, step left
- Push 2, step left
- Push 1, step left
- Nothing on the left: pop and visit 1, then go right
- Nothing on the left: pop and visit 2, then go right
- Push 3, step left
- Nothing on the left: pop and visit 3, then go right
- Nothing on the left: pop and visit 4, then go right
- Push 6, step left
- Nothing on the left: pop and visit 6, then go right
- Push 7, step left
- Nothing on the left: pop and visit 7, then go right
- Stack empty and no node left: [1,2,3,4,6,7], sorted
- Each node pushed and popped once: O(n) time, O(h) stack
04Asked at Google
8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Binary Tree Inorder Traversal | Easy | 42 | last 6 months |
| Kth Smallest Element in a BST | Medium | 41 | last 6 months |
| Validate Binary Search Tree | Medium | 36 | last 6 months |
| Flatten Binary Tree to Linked List | Medium | 33 | last 6 months |
| Binary Search Tree Iterator | Medium | 29 | |
| Binary Tree Preorder Traversal | Easy | 28 | last 6 months |
| Closest Binary Search Tree Value | Easy | 18 | |
| Binary Tree Postorder Traversal | Easy | 13 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.