Iterative Inorder with Stack
You'll learn how to perform inorder traversal without recursion by manually managing a stack to track your position in the tree.
The Core Idea
In recursive inorder, the call stack automatically remembers where you are while you explore left subtrees. To do this iteratively, you explicitly use a stack data structure to simulate that behavior.
The pattern follows these steps:
- Go left as far as possible, pushing each node onto the stack
- When you can't go left anymore (hit
null), pop from the stack - Process that popped node (print it, collect it, etc.)
- Move to its right child and repeat
Think of it like exploring a maze: you keep going left, leaving breadcrumbs (the stack) so you can backtrack when you hit a dead-end, then try the right path.
Why This Works
The stack holds nodes whose left subtrees are either being explored or already finished. When you pop a node, you know its left subtree is done, so it's time to process that node (the "root" part of "Left-Root-Right"), then explore its right subtree.
The Algorithm Pattern
Initialize empty stack
Set current = root
While current is not null OR stack is not empty:
While current is not null:
Push current onto stack
Move current to current.left
Pop node from stack
Process node (print, collect, etc.)
Move current to node.right
The outer loop continues until both the current node is exhausted AND there's nothing left to backtrack to in the stack.
Key Takeaway: Iterative inorder uses a stack to simulate recursion—push while going left, pop to process, then move right—achieving Left-Root-Right order without recursive calls.