The Matrix: Recursive vs Iterative Inorder Traversal Explained

The Quest Begins (The "Why")

I still remember the first time I was asked in an interview to “print the nodes of a binary tree in sorted order.” I stared at the whiteboard, scribbled a recursive solution, and then panicked when the interviewer asked, “Can you do it without recursion?” My brain felt like it was stuck in a loading screen—loading… loading…—and I had no idea how to break out of it.

That moment sparked a quest: understand why inorder traversal gives you a sorted sequence for a binary search tree (BST), and then wield both the recursive and iterative versions like a seasoned adventurer. If you’ve ever felt trapped between recursion’s elegance and iteration’s control, you’re in the right place.

The Revelation (The Insight)

Here’s the magic: inorder traversal visits nodes in the order left‑subtree → root → right‑subtree. For a BST, every node in the left subtree is smaller than the root, and every node in the right subtree is larger. So, if you recursively (or iteratively) walk left first, you’ll encounter the smallest values before the root, then the larger ones after. The traversal naturally yields ascending order—no extra sorting needed.

Why does this work? Think of the BST as a layered onion. Each recursive call peels away the outer layer (the leftmost path) until you hit the smallest leaf, then you “pop” back up, visiting each parent exactly when all its smaller descendants have already been processed. The call stack (or an explicit stack) holds the promise to return to those parents later. That promise is the why: the stack remembers where we need to come back to after exhausting a subtree.

Wielding the Power (Code & Examples)

Recursive version – the classic spell

def inorder_recursive(node):
    if not node:
        return
    inorder_recursive(node.left)   # go deep left
    print(node.val)                # visit the root
    inorder_recursive(node.right)  # then right

Why it feels clean: the call stack does the back‑tracking for us. Each call waits for its left child to finish before printing itself, then proceeds right.

Iterative version – taking control with our own stack

def inorder_iterative(root):
    stack = []
    curr = root
    while curr or stack:
        # Reach the leftmost node of the current subtree
        while curr:
            stack.append(curr)
            curr = curr.left          # <-- trap: forgetting this inner loop loses nodes
        curr = stack.pop()
        print(curr.val)              # visit the node
        curr = curr.right            # move to the right subtree

Common mistake #1: Forgetting the inner while curr: loop. If you only push the current node once, you’ll skip entire left sub‑trees and miss values.

Mistake #2: Pushing right before left (or vice‑versa) without adjusting the traversal order—this turns inorder into preorder or postorder.

Both versions touch each node exactly once → O(n) time.

Space usage:

• Recursive: O(h) call‑stack depth, where h is tree height (worst‑case O(n) for a skewed tree).
• Iterative: O(h) explicit stack (same worst‑case).

Real‑world interview problems that love inorder

1. Validate Binary Search Tree An inorder traversal of a BST must be strictly increasing. Walk the tree iteratively, keep track of the previous value, and ensure curr.val > prev. One pass, O(n) time, O(h) space.

   def is_valid_bst(root):
       stack, prev = [], float('-inf')
       curr = root
       while curr or stack:
           while curr:
               stack.append(curr)
               curr = curr.left
           curr = stack.pop()
           if curr.val <= prev:          # violation!
               return False
           prev = curr.val
           curr = curr.right
       return True

1. Kth Smallest Element in a BST Stop the inorder walk after you’ve visited k nodes.

   def kth_smallest(root, k):
       stack = []
       curr = root
       while curr or stack:
           while curr:
               stack.append(curr)
               curr = curr.left
           curr = stack.pop()
           k -= 1
           if k == 0:
               return curr.val
           curr = curr.right
       return None   # k larger than number of nodes

Both problems become trivial once you see inorder as the “sorted list” generator.

Why This New Power Matters

Now you can:

• Validate BSTs without extra space for copying values.
• Find order statistics (kth smallest/largest) in linear time.
• Flatten a BST into a sorted list or linked list with a single pass.

Understanding the why behind the traversal lets you adapt it to postorder, preorder, or even level‑order when the interview throws a curveball. You’re no longer memorizing a pattern; you’re wielding a fundamental property of binary search trees.

Your Next Challenge

Take the iterative inorder code above and transform it into an iterative postorder traversal (left → right → root) using only one stack. Hint: you’ll need to track whether a node’s children have been processed. Give it a try, share your solution in the comments, and let’s keep the adventure going!

Happy coding, and may your stacks never overflow! 🚀