1. One-Liner
Iterative inorder visits a binary tree in left → root → right order using an explicit stack instead of the call stack.
2. The Problem It Solves
Recursive inorder is simple but risks stack overflow on deep trees and hides state in the runtime. Iterative form gives O(h) auxiliary space you control, same output, and is standard in interviews and embedded settings.
3. The Core Idea
Descend left as far as possible, pushing nodes on a stack. When you cannot go left, pop: that node is the next inorder visit, then continue from its right subtree. This mirrors recursion’s “finish left, visit node, go right”.
4. How It Works (Step-by-Step)
| Step | Action |
|---|
| 1 | Initialize empty stack; set cur = root. |
|---|
| 2 | While cur exists: push cur, cur = cur.left. |
|---|
| 3 | If cur is null and stack not empty: pop → visit value; cur = popped.right. |
|---|
| 4 | Repeat until cur is null and stack is empty. |
|---|
| 5 | Collected order is inorder. |
|---|
5. Dry Run Example
Tree: root 1, left 2, right 3; node 2 has right child 4.
| Phase | cur | stack (top→) | output |
|---|
| Go left | 1→2 | [1,2] | [] |
|---|
| Pop 2, visit | 4 | [1] | [2] |
|---|
| Go left from 4 | null | [1,4] | [2] |
|---|
| Pop 4, visit | null | [1] | [2,4] |
|---|
| Pop 1, visit | 3 | [] | [2,4,1] |
|---|
| Visit 3 | — | [] | 2,4,1,3 |
|---|
6. Key Properties
| Property | Detail |
|---|
| Order | Sorted for BST (inorder) |
|---|
| Space | O(h) stack, h = height |
|---|
| Time | O(n) — each node pushed/popped once |
|---|
| vs Morris | Morris uses O(1) space but mutates links |
|---|
7. Where It Is Used
| Domain | Use |
|---|
| Compilers | Expression trees → infix order |
|---|
| BST | Sorted enumeration without recursion |
|---|
| Debuggers | Tree pretty-print / flatten workflows |
|---|
8. Interview Tips
Know why the loop is while cur or stack. Be ready to code preorder and postorder iterative variants. Discuss BST validation using inorder “previous pointer”. Avoid infinite loops when cur is reassigned after pop.
9. Comparison with Other Algorithms
| Method | Space | Notes |
|---|
| Recursive inorder | O(h) call stack | Simpler code |
|---|
| Iterative + stack | O(h) explicit | Same bounds, more control |
|---|
| Morris | O(1) | Threaded tree trick |
|---|
10. Complexity
| |
|---|
| -- | -- |
|---|
| Time | O(n) |
|---|
| Space | O(h) worst O(n) skewed tree |
|---|
Implementation Example (PYTHON)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder_iterative(root):
out, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return out