The Lord of the Rings: Traversing Trees Like Gandalf

The Quest Begins (The "Why")

I still remember the first time I was asked to print the values of a binary tree in sorted order during an interview. My brain froze. I knew recursion was the go‑to solution, but the interviewer kept probing: “Can you do it without recursion? What’s the trade‑off?” I felt like I was standing at the foot of Mount Doom, staring at a rope bridge I’d never crossed. The problem wasn’t just about writing code—it was about understanding why we visit nodes in a particular order and how we can mimic that order with our own stack instead of the call stack. That curiosity turned a frustrating whiteboard session into a mini‑adventure, and I’m excited to share the map I drew.

The Revelation (The Insight)

At its heart, an inorder traversal (left‑node‑right) is just a way to walk a binary search tree so that the keys come out in ascending order. The magic isn’t in the recursion itself; it’s in the promise we make to ourselves: visit the left subtree, then the current node, then the right subtree. If we honor that promise for every node, the whole tree yields a sorted sequence.

Why does that work? Think of each node as a tiny gatekeeper. All keys in its left subtree are smaller than the node’s key, and all keys in its right subtree are larger. By first exhausting the left side, we guarantee we’ve output every smaller value before we ever touch the node. After the node, we only see larger values. Apply that rule recursively (or iteratively) and the entire tree walks itself into order.

The iterative version simply replaces the implicit call stack with an explicit one we control. We push nodes as we dive left, and when we can’t go left any more, we pop, visit the node, then switch to its right child. The stack remembers where we need to return after finishing a left branch—exactly what the call stack would have done for us.

Wielding the Power (Code & Examples)

The recursive version (the comfortable spell)

function inorderRecursive(node, result = []) {
  if (!node) return result;
  inorderRecursive(node.left, result);
  result.push(node.val);
  inorderRecursive(node.right, result);
  return result;
}

It’s short, readable, and relies on the language’s call stack. In an interview, you can write this in under a minute and move on—if the interviewer is satisfied with recursion.

The iterative version (the heroic feat)

function inorderIterative(root) {
  const stack = [];
  const result = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    // Go as far left as possible, remembering the path
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    // No more left child → visit the node on top of the stack
    current = stack.pop();
    result.push(current.val);
    // Now explore the right subtree
    current = current.right;
  }
  return result;
}

Why this works:

• The inner while pushes every ancestor of the next node to visit, mimicking the descent of recursion.
• When we can’t go left, the top of the stack is the node whose left subtree is fully processed—exactly the node recursion would “return” to.
• After visiting it, we set current to its right child, letting the outer loop repeat the process for that subtree.

Common traps (the lurking trolls)

1. Forgetting to reset current after popping – If you leave current pointing at the popped node, the inner loop will push it again, causing an infinite loop.
2. Using push on the result before visiting the node – That would output a node before its left subtree, breaking the inorder guarantee.
3. Assuming the tree is balanced – The algorithm’s complexity does not depend on shape; it visits each node exactly once, so O(n) holds even for a degenerate list‑like tree.

Interview‑style problems you can now crush

• “Validate a Binary Search Tree” – An inorder traversal of a BST must be strictly increasing. Perform an iterative inorder walk and ensure each value is greater than the previous; O(n) time, O(h) space (where h is tree height).
• “Kth Smallest Element in a BST” – Stop the inorder traversal after you’ve visited k nodes; the kth visited value is the answer. Again, O(n) worst‑case, O(h) space, and you can early‑exit for a win.

Why This New Power Matters

Mastering the iterative inorder traversal does more than check a box on a coding interview. It gives you a mental model for any depth‑first search where you need explicit control over backtracking—think graph algorithms, expression tree evaluation, or even parsing nested JSON. You’ll stop seeing recursion as a black box and start appreciating the underlying mechanics, which makes debugging easier and lets you optimize space when the call stack would blow up (e.g., a tree with 10⁵ nodes skewed to one side).

Plus, there’s a genuine thrill in watching your own stack replace the language’s hidden one. It feels like you’ve forged a new weapon in your arsenal—a tool that works whether you’re coding in JavaScript, Python, C++, or even bash (yes, you can simulate a stack with arrays!). That confidence turns a nervous interview into a chance to showcase depth of understanding.

Your Turn

Grab a binary tree (you can generate one randomly or draw a small one on paper) and write the iterative inorder traversal in your favorite language. Try to add an early exit for the kth smallest problem and test it on a skewed tree versus a balanced one. Did you feel the same “aha!” I did when the output matched the sorted order? Share your snippet or a quick tweet—let’s keep the quest going!

Happy coding, and may your stacks never overflow. 🚀