May the Forest Be With You: Tree Traversals Explained — Recursive vs Iterative

The Quest Begins (The "Why")

I still remember the first time I faced a binary tree in an interview. The interviewer slid a whiteboard marker across the table and said, “Print the nodes in‑order without using recursion.” My stomach dropped. I could write the recursive version in my sleep, but the iterative one felt like trying to solve a Rubik’s Cube blindfolded. I spent three hours sketching stacks, muttering about “parent pointers,” and ended up with a mess of off‑by‑one errors that made me feel like I’d just lost a boss fight in Dark Souls — frustrating, but oddly motivating.

Why does this matter? Tree traversals pop up everywhere: parsing expressions, validating BSTs, serializing data, even AI game trees. If you can’t move through a tree confidently, you’ll keep hitting the same wall in interview after interview. The goal of this article is to turn that wall into a doorway — by showing you why the iterative inorder traversal works, not just how to type it out.

The Revelation (The Insight)

The magic behind the iterative inorder traversal is simple when you think about it like a depth‑first walk with an explicit stack. In the recursive version, the call stack does the heavy lifting: each call remembers where to return after exploring the left subtree, then visits the node, then dives right.

If we replace that implicit call stack with an explicit list (or Deque) we get the same behavior, but we control it ourselves. The algorithm can be summed up in two steps:

1. Go as far left as possible, pushing every node you pass onto the stack.
2. When you can’t go left anymore, pop the top node — this is the next node to visit (because everything left of it has already been processed). Visit it, then move to its right child and repeat.

That’s it. The loop continues until both the current pointer is None and the stack is empty. The insight is that the stack holds exactly the “return addresses” the recursive version would have kept. By managing them manually we avoid the function‑call overhead and, more importantly for interviews, we demonstrate we understand the underlying mechanics.

Wielding the Power (Code & Examples)

The Struggle – A Naïve Recursive Attempt (and why it fails the interview)

def inorder_recursive(root):
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

This works, but the interviewer asked for no recursion. If you present this, you’ll likely hear, “Great, now can you do it without the call stack?” — and you’ll be back to square one.

The Victory – Iterative Inorder Traversal

def inorder_iterative(root):
    result = []
    stack = []          # our explicit call stack
    curr = root

    while curr or stack:
        # 1️⃣ Push all left children
        while curr:
            stack.append(curr)
            curr = curr.left

        # 2️⃣ Pop the node, visit it, then go right
        curr = stack.pop()
        result.append(curr.val)   # <-- visit step
        curr = curr.right         # move to right subtree

    return result

Why this works:

• The inner while curr: loop drives us down the leftmost path, stacking nodes we haven’t yet visited.
• When curr becomes None, the top of the stack is the nearest ancestor whose left subtree is exhausted — exactly the node the recursive version would “return to” after its left call.
• We pop it, record its value (the visit), and then set curr to its right child, repeating the process.

If you trace the algorithm on a small tree, you’ll see the stack mimic the recursive call stack step for step.

Common Traps (The “Boss Moves” to Avoid)

Trap	What happens	How to dodge it
Forgetting to reset curr after popping	You’ll keep re‑popping the same node → infinite loop	Always set curr = curr.right after you’ve processed the popped node
Pushing the right child too early	You’ll visit nodes out of order (pre‑order‑ish)	Only push left children in the inner loop; right children are handled via the curr = curr.right step after a pop
Using pop(0) on a list (queue)	Turns the algorithm into O(n²) because each pop shifts elements	Use append/pop on the end of the list – O(1) per operation

Real‑World Interview Flavors

1. Validate a Binary Search Tree – An inorder traversal of a BST yields a strictly increasing sequence. With the iterative version you can check the property on the fly, using O(h) extra space instead of O(n) for the recursion stack.

2. Kth Smallest Element in a BST – Stop the traversal after you’ve visited k nodes. The iterative approach lets you break out early without unwinding recursive calls, which is a frequent follow‑up question.

Both problems love the iterative pattern because it gives you explicit control over when to stop or inspect state.

Why This New Power Matters

Now that you’ve got the iterative inorder traversal in your toolkit, you can:

• Ace interview questions that explicitly forbid recursion (a classic way to test depth of understanding).
• Write safer production code where deep trees could blow the call stack (think 10⁵‑node trees in a language with limited recursion depth).
• Combine it with other patterns — early exits, stateful accumulators, or even converting the traversal into a generator for lazy processing.

In short, you’ve moved from “I can recite the recipe” to “I understand why the recipe works.” That shift is the difference between memorizing answers and solving problems — exactly what interviewers (and teammates) love to see.

Your Turn

Grab a binary tree (draw one on paper or code a quick random generator) and try to print its postorder traversal iteratively using two stacks or one stack with a visited flag. Feel the same click you got with inorder? If you do, drop a comment with your solution or a question — let’s keep the quest going!

Happy traversing! 🚀