Recursive tree traversals are a dangerous crutch if you don't

Most of us just memorize the "left, node, right" pattern for inorder traversals and copy-paste the recursive boilerplate without a second thought. But the moment you're dealing with a skewed tree or a massive dataset, that elegant recursion becomes a liability. If your tree is a straight line of 100,000 nodes, you aren't looking at an elegant solution—you're looking at a StackOverflowError.

The real breakthrough happens when you realize that recursion is just a hidden stack. Every time a function calls itself, the system pushes a frame onto the call stack to remember where to return. If you can mimic that behavior with an explicit data structure, you can convert any recursive traversal into an iterative one. It's not a "hack"; it's just moving the memory management from the JVM/runtime into your own code.

The logic behind the iterative shift

To do an inorder traversal without recursion, you have to manually manage the "breadcrumb trail." The logic follows a specific loop:

1. Use a stack to track the path.
2. Drill down as far left as possible, pushing every node you encounter onto the stack.
3. Once you hit a null (the end of the left branch), pop the stack. This node is officially the "leftmost" available node.
4. Visit that node, then pivot to its right child and start the process over.

This ensures that the left subtree is entirely exhausted before the parent is processed, and the parent is processed before the right subtree. It's a mirror image of the recursive flow, but it's safer for deep trees.

Implementation and Gotchas

Here is the recursive baseline we usually start with:

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

Now, here is the iterative version. I prefer using ArrayDeque over the old Stack class in Java for 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; 
 }
}

If you're implementing this from scratch, watch out for these two common bugs:

• The Infinite Loop: If you forget cur = cur.right; after popping, the outer loop will see that cur is still the node you just visited, try to go left again, and you'll end up in a cycle.
• Push Order: If you push the right child before the left, you're no longer doing an inorder traversal—you're essentially reversing the logic.

For anyone building a real-world AI workflow or custom LLM agent that needs to parse hierarchical data structures, mastering these iterative patterns is a must. It ensures your deployment is stable regardless of the input tree depth.