Recursive tree traversals can become dangerous when recursion goes unchecked

Most of us memorize the "left, node, right" pattern for inorder traversals, then copy and paste the recursive boilerplate without thinking twice. However, once a tree is skewed or the dataset becomes massive, that elegant recursion turns into a liability. A straight-line tree of 100,000 nodes does not produce an elegant solution—it produces a StackOverflowError.

Recursion is a hidden stack

The key realization is that recursion is simply a hidden stack. Each time a function calls itself, the system pushes a frame onto the call stack to record where execution should resume. By reproducing that behavior with an explicit data structure, you can turn any recursive traversal into an iterative one. This is not a "hack"; it is simply moving memory management out of the JVM/runtime and into your own code.

The logic behind the iterative shift

Manual breadcrumb trail for traversal

An inorder traversal without recursion requires you to manage the "breadcrumb trail" manually. The loop follows a specific sequence:

1. Use a stack to keep track of the path.
2. Move as far left as possible, pushing each node onto the stack.
3. When you reach null, the end of the left branch, pop the stack. This is the "leftmost" available node.
4. Visit the node, move to its right child, and begin again.

This process finishes the left subtree before processing the parent, then processes the parent before moving into the right subtree. That is the recursive flow mirrored with an explicit structure, making it safer for deep trees.

Implementation and Gotchas

We usually begin with this recursive baseline:

void inorderRecursive(TreeNode node) {
 if (node == null) return;
 inorderRecursive(node.left);
 visit(node); 
 inorderRecursive(node.right);
}

Iterative version with ArrayDeque

Here is the iterative version. In Java, I prefer ArrayDeque over the old Stack class because it offers better performance.

void inorderIterative(TreeNode root) {
 Deque<TreeNode> stack = new ArrayDeque<>();
 TreeNode cur = root;

 while (cur != null || !stack.isEmpty()) {
 // Exhaust the left branch
 while (cur != null) {
 stack.push(cur);
 cur = cur.left;
 }
 
 // Backtrack to the parent
 cur = stack.pop();
 visit(cur); 
 
 // Shift to the right subtree
 cur = cur.right; 
 }
}

Two common bugs to avoid

When implementing this from scratch, watch for two common bugs:

• The Infinite Loop: If you forget cur = cur.right; after popping, the outer loop still sees cur as the node you just visited, attempts to go left again, and enters a cycle.
• Push Order: Pushing the right child before the left means you are no longer performing an inorder traversal; you are effectively reversing the logic.

For anyone building a real-world AI workflow or custom LLM agent that parses hierarchical data structures, mastering these iterative patterns is essential. This keeps deployments stable regardless of input tree depth.