LeetCode 94: Binary Tree Inorder Traversal

In our recent deep dive into Binary Search Trees, we learned that Inorder Traversal is the "magic key" that gives us a sorted list for free.

Today, we're going to solve LeetCode 94 and implement this traversal in two ways:

Recursively (The intuitive "Human" way)
Iteratively (The manual "Machine" way using a Stack)

🧩 The Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Recall the Rule: Left → Root → Right.

Example:

Input: root = [1,null,2,3]
Output: [1,3,2]

   1
    \
     2
    /
   3

🧠 Solution 1: The Recursive Approach (The Intuitive Way)

Recursion is the natural way to solve tree problems because trees are recursive structures.

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    
    const traverse = (node) => {
        if (!node) return;
        
        traverse(node.left);  // 1. Keep going LEFT
        res.push(node.val);   // 2. Visit ROOT
        traverse(node.right); // 3. Go RIGHT
    };
    
    traverse(root);
    return res;
};

Why this works:

Every time we call traverse(node.left), the computer pauses the current function and puts it on the Call Stack. It stays there until the left side is completely done. This is effectively "saving our place" so we can come back and visit the root later.

🧱 Solution 2: The Iterative Approach (The "Follow-up" Challenge)

The LeetCode follow-up asks: "Recursive solution is trivial, could you do it iteratively?"

To do this, we have to manually manage the stack that the computer usually handles for us hidden behind the scenes.

var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let curr = root;
 
    while (curr !== null || stack.length > 0) {
        // 1. Go as far LEFT as possible, pushing nodes onto the stack
        while (curr !== null) {
            stack.push(curr);
            curr = curr.left;
        }
 
        // 2. No more left? Pop the last node (the ROOT of this subtree)
        curr = stack.pop();
        res.push(curr.val);
 
        // 3. Now try to go RIGHT
        curr = curr.right;
    }
 
    return res;
};

How the Iterative Logic Works:

Phase 1: We keep pushing to the stack as we dive left.
Phase 2: Once we hit null, we know we've reached the leftmost boundary. We pop() to get back to the parent.
Phase 3: We record that parent’s value and then try to dive into its right child to repeat the process.

📊 Comparison

Feature	Recursive	Iterative
Logic	Intuitive	Manual state management
Time Complexity	O(n)	O(n)
Space Complexity	O(h) (Call Stack)	O(h) (Explicit Stack)
Memory Risk	Stack Overflow on deep trees	Better memory control

🏁 Summary

The Recursive version is elegant and helps you understand the concept of DFS. The Iterative version is powerful because it shows you exactly how the computer handles that recursion under the hood.

Want more? Try solving LeetCode 144 (Preorder) and LeetCode 145 (Postorder) using the same iterative stack pattern. You'll find it's just a small logical tweak!

Leetcode 94 Binary Tree Inorder Traversal Recursive Vs Iterative