Solving Binary Tree Inorder Traversal in JavaScript: Step-by-Step Guide

Binary tree traversal is one of the foundational skills every JavaScript developer should master, especially if you are preparing for technical interviews or building data-intensive applications. Among the three depth-first traversal strategies — preorder, inorder, and postorder — inorder traversal holds a special place because of its unique relationship with Binary Search Trees (BSTs). In this tutorial, we will walk through everything you need to know to confidently solve the Binary Tree Inorder Traversal problem in JavaScript.

What Is Inorder Traversal?

Inorder traversal is a depth-first traversal technique where nodes of a binary tree are visited in the following order:

First, recursively traverse the left subtree.
Then, visit the root node.
Finally, recursively traverse the right subtree.

This left-root-right pattern produces a sorted sequence when applied to a valid Binary Search Tree, which is one of the main reasons inorder traversal is so widely used.

Why Inorder Traversal Matters

Understanding inorder traversal matters for several practical reasons:

BST validation: The output of an inorder traversal on a BST should be strictly increasing, making it easy to verify tree validity.
Sorted output: For BSTs, inorder traversal yields nodes in ascending order without additional sorting.
Interview relevance: It is one of the most frequently asked tree problems on platforms like LeetCode.
Foundation for advanced algorithms: Many tree manipulation algorithms, such as finding the kth smallest element or recovering a swapped BST, build on inorder traversal.

Defining the Binary Tree Node

Before writing any traversal logic, we need a simple representation of a binary tree node. In JavaScript, this is typically done using a class:

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Example tree:
//       1
//        \
//         2
//        /
//       3
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);

This structure gives us a val to store data and left and right pointers to child nodes. With this in place, we can move on to the actual traversal implementations.

Approach 1: Recursive Solution

The recursive approach is the most intuitive way to perform an inorder traversal. It directly mirrors the definition: traverse left, visit root, traverse right. We use a helper function to accumulate values into a result array.

function inorderTraversalRecursive(root) {
  const result = [];

  function traverse(node) {
    if (node === null) return;
    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

console.log(inorderTraversalRecursive(root)); // [1, 3, 2]

This solution is clean and easy to reason about. The time complexity is O(n) because each node is visited exactly once, and the space complexity is O(n) in the worst case due to the recursion stack, which can grow as deep as the height of the tree.

Approach 2: Iterative Solution Using a Stack

While recursion is elegant, it can cause stack overflow errors on very deep trees. The iterative approach simulates recursion using an explicit stack. The idea is to push all left children onto the stack until we reach a leaf, then pop, process, and move to the right subtree.

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

  while (current !== null || stack.length > 0) {
    // Go as far left as possible
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // Process the node
    current = stack.pop();
    result.push(current.val);

    // Move to the right subtree
    current = current.right;
  }

  return result;
}

console.log(inorderTraversalIterative(root)); // [1, 3, 2]

This iterative version also runs in O(n) time and uses O(n) space in the worst case. However, it avoids the hidden cost of recursive call frames and is generally preferred in production code where tree depth may be unpredictable.

Approach 3: Morris Traversal for O(1) Space

For advanced use cases where memory is constrained, Morris Traversal offers an ingenious way to perform inorder traversal using only O(1) extra space. It temporarily modifies the tree by creating links from predecessor nodes back to the current node, then restores the tree as it traverses.

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

  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.right;
    } else {
      // Find the inorder predecessor
      let predecessor = current.left;
      while (predecessor.right !== null && predecessor.right !== current) {
        predecessor = predecessor.right;
      }

      if (predecessor.right === null) {
        // Create a temporary link back to current
        predecessor.right = current;
        current = current.left;
      } else {
        // Revert the temporary link
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }

  return result;
}

console.log(inorderTraversalMorris(root)); // [1, 3, 2]

Morris Traversal is a great tool to know for interviews, as it demonstrates a deep understanding of tree structure and pointer manipulation. However, it is more complex and harder to debug, so use it judiciously.

Best Practices

Choose the right approach: Use recursion for clarity in small trees, iteration for safety in deep trees, and Morris traversal when memory is critical.
Handle edge cases: Always account for an empty tree (root === null) and trees with only one node.
Avoid global state: Pass the result array through helper functions rather than relying on outer variables, which can cause bugs in concurrent or repeated calls.
Test with varied inputs: Validate your solution against skewed trees, balanced trees, and BSTs to ensure correctness.
Understand the trade-offs: Know the time and space complexity of each approach so you can justify your choice in interviews.

Common Pitfalls to Avoid

When implementing inorder traversal, developers often run into a few recurring mistakes. One common error is forgetting to update the current pointer after popping from the stack in the iterative approach, which leads to infinite loops. Another is mutating the tree unintentionally in Morris Traversal by forgetting to restore the temporary links. Finally, be careful with JavaScript's reference semantics — pushing nodes directly into the result array instead of their values will produce unexpected output.

Conclusion

Binary tree inorder traversal is a deceptively simple problem that reveals a great deal about a developer's understanding of recursion, stacks, and tree structures. By mastering the recursive, iterative, and Morris traversal approaches in JavaScript, you equip yourself with versatile tools that apply far beyond this single problem. Start with the recursive solution to build intuition, move to the iterative version for robustness, and explore Morris traversal when you want to push your skills further. With consistent practice and attention to edge cases, inorder traversal will become second nature and a reliable asset in your programming toolkit.