May the Traversals Be With You: Recursive vs Iterative Inorder Traversal

The Quest Begins (The "Why")

I was prepping for a senior‑engineer interview when the interviewer tossed a seemingly innocent question: “Give me the inorder traversal of a binary tree without using recursion.” My brain instantly flashed to the clean recursive solution I’d written a dozen times, but then the whiteboard stared back at me, demanding an iterative version. I felt like Luke Skywalker facing the Death Star trench—knowing the force (recursion) was strong, but needing to rely on my own piloting skills (an explicit stack) to succeed.

Why does this matter? Because interviewers love to see if you understand the why behind a technique, not just memorize a pattern. Recursive tree traversals are elegant, but they hide a cost: each call adds a frame to the call stack. In a skewed tree (think a linked list disguised as a tree) that depth can blow up to O(n) and trigger a stack overflow. An iterative approach puts you in control of the stack, letting you handle arbitrarily deep trees safely.

The Revelation (The Insight)

The secret sauce is simple: inorder traversal visits nodes in the order left‑subtree → node → right‑subtree. Recursively, we express that as three steps: traverse left, visit the node, traverse right. To turn that into an iterative algorithm we mimic the call stack with our own Stack<Node>.

We start at the root and push nodes onto the stack as we go left as far as possible. When we can’t go left any further, we pop the top node—this is the next node to visit (because everything left of it has already been processed). After visiting it, we switch to its right child and repeat the left‑push loop. The loop ends when both the stack is empty and the current pointer is null.

Why does this give us inorder? Imagine the stack as a trail of breadcrumbs marking every ancestor we’ve yet to finish processing. By always diving left first, we ensure that when we pop a node, its entire left subtree has already been output. The node itself is output next, and then we begin exploring its right subtree in the same way. It’s exactly the same order the recursive calls would produce, just made explicit.

Wielding the Power (Code & Examples)

The Recursive Baseline (the “struggle”)

// Simple recursive inorder – clean but uses the call stack
void inorderRecursive(Node root) {
    if (root == null) return;
    inorderRecursive(root.left);
    System.out.print(root.val + " ");
    inorderRecursive(root.right);
}

This works fine for balanced trees, but if the tree is a straight line (all nodes only have a right child) the recursion depth equals n. On a machine with a modest stack size, a tree of 10⁵ nodes will throw a StackOverflowError.

The Iterative Victory (the “after”)

// Iterative inorder using an explicit stack – O(n) time, O(h) space
void inorderIterative(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    Node curr = root;

    while (curr != null || !stack.isEmpty()) {
        // Go as far left as possible, pushing ancestors
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // curr is null here, so we pop the next node to visit
        curr = stack.pop();
        System.out.print(curr.val + " ");
        // Now visit the right subtree
        curr = curr.right;
    }
}

What to watch out for:

• Forgetting to reset curr after popping – if you leave curr as the popped node, the inner left‑push loop will re‑push the same node forever.
• Using a Stack class that’s synchronized – in performance‑critical code prefer ArrayDeque (as shown) because it’s faster and non‑blocking.

Interview‑Style Problems

1. Binary Tree Inorder Traversal (LeetCode 94) – classic. The iterative solution above is the expected answer when the interviewer explicitly bans recursion.

2. Kth Smallest Element in a BST (LeetCode 230) – you can reuse the same loop, keeping a counter. When the counter hits k, return the node’s value. No extra space beyond the stack.

Both run in O(n) time because each node is pushed and popped exactly once. The auxiliary space is O(h) where h is the tree height (worst‑case O(n) for a skewed tree, best‑case O(log n) for a balanced tree).

Why This New Power Matters

Mastering the explicit‑stack pattern does more than pass an interview question—it gives you a mental toolkit for any situation where recursion risks blowing the stack: parsing nested expressions, iterating over file directories, or even implementing your own undo/redo mechanism. You’ll start seeing the call stack as just another data structure you can manipulate, which is incredibly empowering.

Plus, you’ll impress interviewers by showing you understand the trade‑offs: readability vs. safety, and you’ll be able to explain why you chose one approach over the other on the spot.

Your Turn

Grab a binary tree (draw one on paper or whip up a quick generator) and try to walk through the iterative algorithm manually for a few nodes. Then code it up in your favorite language and test it on a degenerate tree of 10⁵ nodes—watch it run without a single stack overflow.

If you’re feeling adventurous, modify the loop to collect nodes in a list and return the kth element without extra traversals.

What other recursive tree patterns have you turned into iterative wins? Drop your thoughts in the comments—I’d love to hear your quest stories!