May the Traversal Be With You: Inorder Tree Traversal Explained

The Quest Begins (The "Why")

I still remember the first time I was asked to “print the values of a binary search tree in sorted order” during a coding interview. My brain went blank. I knew the tree had a left‑child, a right‑child, and a value, but how do you walk through it without getting lost in a maze of pointers? I tried a naive loop, missed nodes, and ended up with a half‑sorted list that made the interviewer raise an eyebrow. That moment felt like staring at a locked door while the clock ticked down—frustrating, but also a spark: there had to be a clean, reliable way to visit every node exactly once and come out with the numbers in order.

That’s the heart of the problem: how do we traverse a tree so that we visit left subtree, then the node itself, then right subtree? It’s called inorder traversal, and when the tree is a BST, the visited sequence is automatically sorted. Nail this, and a whole class of interview questions becomes trivial.

The Revelation (The Insight)

The magic isn’t in some fancy trick—it’s in the call stack. When you write a recursive function, each call pauses and waits for its children to finish before it can continue. That pause is exactly what gives us the left‑root‑right order:

1. Recurse left → you keep going down left children until you hit a null.
2. Visit the node (print/process it).
3. Recurse right → you then explore the right subtree in the same way.

Because each recursive call waits for its left call to finish before it prints its own value, the output naturally respects the left‑before‑node‑before‑right rule.

But recursion isn’t the only way to get that waiting behavior. We can mimic the call stack with an explicit stack data structure. The iterative version does the same three steps, only we push nodes onto the stack ourselves and pop them when it’s time to “visit”.

Why does this work? Think of the stack as a trail of breadcrumbs. As we push left children, we’re marking the path we’ve taken so we can backtrack later. When there’s no left child to go further, we pop the most recent node—this is the node whose left subtree we’ve fully processed—so we can safely visit it now and then move to its right. The process repeats until the stack is empty and every node has been handled exactly once.

It’s like having a magical map that tells you exactly when to turn left, when to stop and admire the view, and when to head right—no guesswork, no missed scenery.

Wielding the Power (Code & Examples)

Let’s see the two versions side by side. I’ll use Python because it reads almost like pseudocode, but the logic translates directly to Java, C++, or JavaScript.

Recursive version

def inorder_recursive(node):
    if not node:
        return
    inorder_recursive(node.left)   # 1. go left
    print(node.val)                # 2. visit node
    inorder_recursive(node.right)  # 3. go right

Iterative version (explicit 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

        # curr is None here, so we pop the last visited node
        curr = stack.pop()
        print(curr.val)            # visit the node

        # now we’ve visited the node and its left subtree,
        # it’s time to look at the right side
        curr = curr.right

Common traps to avoid

• Forgetting the base case in recursion (if not node: return) leads to infinite calls and a stack overflow.
• Mixing up the order of push/pop in the iterative loop—if you pop before pushing all left children, you’ll visit a node too early and break the inorder sequence.
• Neglecting to reset curr after popping—if you leave curr pointing to a left child that’s already been processed, you’ll revisit nodes forever.

Interview problem #1: Validate a Binary Search Tree

A BST is valid iff an inorder traversal yields a strictly increasing sequence. With the iterative version we can check on the fly, using O(h) extra space:

def is_valid_bst(root):
    stack = []
    curr = root
    prev_val = float('-inf')

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        if curr.val <= prev_val:      # violation!
            return False
        prev_val = curr.val
        curr = curr.right

    return True

Time: O(n) – each node pushed and popped once.

Space: O(h) – at most the height of the tree lives on the stack (worst‑case O(n) for a skewed tree, O(log n) for a balanced one).

Interview problem #2: Kth smallest element in a BST

Again, inorder gives us sorted order, so we just stop after k visits:

def kth_smallest(root, k):
    stack = []
    curr = root
    count = 0

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        count += 1
        if count == k:
            return curr.val
        curr = curr.right

    raise ValueError("k is larger than number of nodes")

Same O(n) time, O(h) space.

Why This New Power Matters

Mastering inorder traversal does more than check a box on an interview sheet—it gives you a mental model for any problem that needs ordered output from a hierarchical structure. Think of file systems, expression syntax trees, or even UI component trees where you need to apply a layout pass left‑to‑right. Once you see the pattern “go left, process, go right”, you start spotting it everywhere, and the fear of “getting lost in pointers” evaporates.

You’ve now got two spells in your grimoire: the elegant recursive version (quick to write, relies on the language’s call stack) and the sturdy iterative version (explicit, works in environments where recursion depth is limited, and shines when you need to interleave processing with traversal). Choose the one that fits your constraints, and you’ll walk out of any tree‑related challenge feeling like you’ve just aced a boss fight—victorious, energized, and ready for the next quest.

---

Your turn: Grab a binary search tree (you can generate one randomly or use a simple insert‑only build) and implement both versions. Then try to solve the “Kth smallest” problem without looking at the solution above. Share your code or a snippet in the comments—let’s see who can traverse the forest fastest! 🚀