Inorder Traversal: The Matrix

The Quest Begins (The "Why")

I still remember the first time I was asked to print the nodes of a binary tree in sorted order during a technical interview. My heart raced — not because I feared the whiteboard, but because I knew the answer lay in something called inorder traversal. I’d seen the term in textbooks, but the recursive version felt like a magic spell: you just call the function on the left, visit the node, then call it on the right. It worked, but I had no idea why it produced the sorted order.

When the interviewer followed up with “Can you do it without recursion?” I felt like Neo staring at the blinking cursor, wondering if I could dodge the bullets of a stack overflow. I spent three hours scribbling on paper, trying to simulate the call stack with my own data structure. When the iterative version finally clicked, I felt like I’d just taken the red pill and seen the underlying reality of the tree.

That moment taught me two things:

1. Understanding why an algorithm works is far more powerful than memorizing how to type it.
2. The recursive and iterative solutions are two sides of the same coin — one uses the system stack, the other uses an explicit stack we control.

The Revelation (The Insight)

So why does inorder traversal give you a sorted sequence for a binary search tree (BST)?

Think of a BST as a hierarchy where every left subtree holds values smaller than the node, and every right subtree holds values larger. If you visit left → node → right, you’re essentially saying: “First output everything that’s guaranteed to be smaller, then the node itself, then everything that’s guaranteed to be larger.”

Do that recursively, and each call dives deeper into the leftmost branch until it hits a null, then bubbles up, visiting nodes in increasing order. The call stack implicitly remembers where to return after each left exploration, so you never lose track of where you are.

When we replace the call stack with our own stack, we mimic exactly that behavior:

1. Push the current node and go as far left as possible, pushing each node onto the stack.
2. When you can’t go left any more, pop the top — this is the next smallest node.
3. Visit it, then move to its right child and repeat the left‑push process.

The loop continues until both the current pointer is null and the stack is empty. In other words, we’re performing the same left‑node‑right walk, just managing the “where do I go next?” ourselves.

That’s the core insight: inorder traversal is just a systematic way of walking the tree so that you always process a node after all smaller nodes and before all larger ones. Whether the stack is the CPU’s call stack or a std::vector you manipulate, the order of visits stays identical.

Wielding the Power (Code & Examples)

The Struggle: Recursive Version (the “spell”)

void inorderRecursive(TreeNode* root) {
    if (!root) return;
    inorderRecursive(root->left);
    std::cout << root->val << ' ';
    inorderRecursive(root->right);
}

It’s elegant, but interviewers love to ask: What if the tree is skewed (like a linked list)? The recursion depth becomes O(n), and you risk a stack overflow on large inputs.

The Victory: Iterative Version (the “tech”)

void inorderIterative(TreeNode* root) {
    std::stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != nullptr || !st.empty()) {
        // Go as far left as possible, pushing nodes on the way.
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        // curr is null here, so we pop the next node to visit.
        curr = st.top();
        st.pop();
        std::cout << curr->val << ' ';

        // Now visit the right subtree.
        curr = curr->right;
    }
}

Why it works: The inner while pushes the leftmost path onto st. When we can’t go left, the node on top of the stack is the next smallest — exactly what the recursive call would have returned to after finishing its left subtree. We visit it, then switch to its right child and repeat.

Common traps:

• Forgetting to update curr after popping (leads to an infinite loop).
• Using st.empty() alone in the outer condition without checking curr (you’ll miss the last node).

Interview Problems that Love This

1. Kth Smallest Element in a BST – Perform an inorder traversal and stop when you’ve visited k nodes. The iterative version lets you do this in O(h + k) time and O(h) space, where h is the tree height.
2. Validate BST – An inorder traversal of a valid BST yields a strictly increasing sequence. You can validate on the fly by keeping track of the previously visited value.

Both problems become trivial once you internalize the inorder walk.

Why This New Power Matters

Mastering the iterative inorder traversal does more than check a box on an interview rubric. It gives you a mental model for any depth‑first tree walk: you’re always managing a stack of “nodes to return to later”. Swap the order of pushes and you get preorder or postorder. Change the stack to a queue and you get level‑order (BFS).

In real‑world code, iterative traversals keep your program safe from stack‑overflow on deep trees (think of a file system with millions of nested folders). They also make it easy to inject extra logic — like early termination, logging, or switching between traversal strategies without rewriting recursion.

So next time you stare at a binary tree, remember: you’ve got the red pill in hand. Choose the explicit stack, own the traversal, and watch the nodes line up in perfect order.

---

Your turn: Try implementing an iterative postorder traversal using two stacks (or one stack with a visited flag). Drop your solution in the comments and let’s see who can dodge the bullets of the call stack the most elegantly! 🚀