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

The Quest Begins (The "Why")

Honestly, I still remember the first time I faced a binary tree in an interview and my brain just froze. The interviewer asked, “Can you print the nodes in sorted order without using any extra libraries?” I stared at the whiteboard, heart pounding, as if I were about to face a tough boss, and thought, “There’s got to be a simpler way.” The problem wasn’t just about writing code; it was about understanding why we visit nodes in a particular order. That curiosity turned into a mini‑adventure, and I’m excited to share the map I found.

The Revelation (The Insight)

Here’s the thing: a tree traversal isn’t magic, it’s just a systematic way to walk every node exactly once. The why behind the order comes from the data structure itself. For a Binary Search Tree, an inorder walk (left → root → right) yields the keys in ascending order because every left subtree holds smaller values and every right subtree holds larger values. Think of it like peeling an onion layer by layer: you first get to the core of the left side, then the center, then the right side. When you mimic that process with recursion, each call naturally waits for its left child to finish before processing the node itself, then moves to the right. The call stack is the hidden itinerary that keeps track of where you left off.

If you replace the call stack with an explicit stack, you get the same behavior but you control the itinerary yourself. That’s the iterative version: push nodes as you go left, pop when you can’t go further, visit the node, then switch to its right child. Both versions visit each node exactly once, giving O(n) time, and the extra space is proportional to the height of the tree (O(h)). For a balanced tree that’s O(log n); for a degenerate chain it’s O(n). No matter which flavor you pick, the core idea stays the same: visit left, then node, then right.

Wielding the Power (Code & Examples)

Let’s see the spells in action. First, the recursive version – short, readable, and often the first thing that comes to mind.

function inorderRecursive(node) {
  if (!node) return;
  inorderRecursive(node.left);
  console.log(node.val);   // visit
  inorderRecursive(node.right);
}

Trap #1: Forgetting the base case (if (!node) return) leads to a stack overflow on null children. I spent an hour debugging that once, and when I finally added the guard, it felt like a huge weight lifting.

Now the iterative twin, using an explicit stack. This is the version interviewers love to see because it shows you understand what recursion is doing under the hood.

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