Skip to main content

Binary Tree Inorder Traversal (Iterative)

Given a binary tree, return a list containing its inorder traversal without using recursion.

Example(s)​

Example 1:

Input:
      2     
     / \   
    1   3

Output: [1, 2, 3]
Explanation:
Inorder: left → root → right
1 (left) → 2 (root) → 3 (right)

Example 2:

Input:
        2
       / \
      1   7
     / \
    4   8

Output: [4, 1, 8, 2, 7]
Explanation:
Inorder traversal:
4 (leftmost) → 1 (left) → 8 (right of 1) → 2 (root) → 7 (right)

Example 3:

Input:
      1
       \
        2
       /
      3

Output: [1, 3, 2]
Explanation:
Inorder: 1 (root) → 3 (left of 2) → 2 (right)

Solution​

The solution uses iterative approach with stack:

  1. Use stack: Simulate recursion using a stack
  2. Go left first: Push all left nodes onto stack
  3. Process node: Pop from stack, add to result
  4. Go right: Move to right subtree and repeat

JavaScript Solution - Iterative with Stack

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : null)
* }
*/

/**
* Inorder traversal without recursion
* @param {TreeNode} root - Root of the binary tree
* @return {number[]} - Inorder traversal result
*/
function inorderTraversal(root) {
const result = [];
const stack = [];
let current = root;

while (current !== null || stack.length > 0) {
  // Go to the leftmost node
  while (current !== null) {
    stack.push(current);
    current = current.left;
  }
  
  // Current is null, pop from stack
  current = stack.pop();
  result.push(current.val);
  
  // Visit right subtree
  current = current.right;
}

return result;
}

// Helper function to create TreeNode
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : null);
}

// Test cases
// Example 1: [2,1,3]
const root1 = new TreeNode(2);
root1.left = new TreeNode(1);
root1.right = new TreeNode(3);
console.log('Example 1:', inorderTraversal(root1)); 
// [1, 2, 3]

// Example 2: [2,1,7,4,8]
const root2 = new TreeNode(2);
root2.left = new TreeNode(1);
root2.right = new TreeNode(7);
root2.left.left = new TreeNode(4);
root2.left.right = new TreeNode(8);
console.log('Example 2:', inorderTraversal(root2)); 
// [4, 1, 8, 2, 7]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Morris Traversal)​

Here's a space-optimized version using Morris traversal (O(1) space):

/**
 * Morris traversal - O(1) space
 */
function inorderTraversalMorris(root) {
  const result = [];
  let current = root;
  
  while (current !== null) {
    if (current.left === null) {
      // No left subtree, visit current node
      result.push(current.val);
      current = current.right;
    } else {
      // Find rightmost node in left subtree
      let predecessor = current.left;
      while (predecessor.right !== null && predecessor.right !== current) {
        predecessor = predecessor.right;
      }
      
      if (predecessor.right === null) {
        // Create temporary link
        predecessor.right = current;
        current = current.left;
      } else {
        // Remove temporary link
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  
  return result;
}

Complexity​

  • Time Complexity: O(n) - Where n is the number of nodes. We visit each node exactly once.
  • Space Complexity:
    • Stack approach: O(h) - Where h is the height of the tree (stack size)
    • Morris traversal: O(1) - Only using a constant amount of extra space

Approach​

The solution uses iterative approach with stack:

  1. Initialize:

    • Create result array and stack
    • Start with current = root

  2. Go left:

    • While current is not null, push to stack and go left
    • This reaches the leftmost node

  3. Process node:

    • Pop from stack (leftmost node)
    • Add to result

  4. Go right:

    • Move to right subtree
    • Repeat the process

  5. Continue:

    • Repeat until stack is empty and current is null

Key Insights​

  • Stack simulates recursion: Replaces recursion stack
  • Go left first: Inorder is left → root → right
  • Process when popping: Process node when popping from stack
  • Then go right: After processing, visit right subtree
  • O(n) time: Must visit all nodes

Step-by-Step Example​

Let's trace through Example 1: root = [2,1,3]

Tree:
      2
     / \
    1   3

Initial: current = 2, stack = [], result = []

Iteration 1:
  current = 2 (not null)
  Go left: push 2, current = 1
  current = 1 (not null)
  Go left: push 1, current = null
  
  current = null, pop from stack
  popped = 1
  result.push(1) → result = [1]
  current = 1.right = null

Iteration 2:
  current = null, stack = [2]
  Pop from stack
  popped = 2
  result.push(2) → result = [1, 2]
  current = 2.right = 3

Iteration 3:
  current = 3 (not null)
  Go left: push 3, current = null
  
  current = null, pop from stack
  popped = 3
  result.push(3) → result = [1, 2, 3]
  current = 3.right = null

current = null and stack = [], exit loop

Result: [1, 2, 3]

Visual Representation​

Example 1:
      2
     / \
    1   3

Inorder: left → root → right

Step 1: Go to leftmost (1)
  Stack: [2, 1]
  Process: 1
  Result: [1]

Step 2: Process root (2)
  Stack: [2]
  Process: 2
  Result: [1, 2]

Step 3: Go to right (3)
  Stack: [3]
  Process: 3
  Result: [1, 2, 3]

Example 2:
        2
       / \
      1   7
     / \
    4   8

Inorder: 4 → 1 → 8 → 2 → 7

Traversal order:
  1. Go leftmost: 4
  2. Backtrack: 1
  3. Go right: 8
  4. Backtrack: 2
  5. Go right: 7

Edge Cases​

  • Empty tree: Return empty list
  • Single node: Return [node.val]
  • Left-skewed tree: Works correctly
  • Right-skewed tree: Works correctly
  • Perfect tree: Works correctly

Important Notes​

  • No recursion: Must use iterative approach
  • Stack required: Simulates recursion stack
  • Inorder order: Left → Root → Right
  • O(h) space: Stack size equals tree height
  • O(n) time: Must visit all nodes

Why Stack Works​

Key insight:

  • Recursion uses a call stack
  • We can simulate this with an explicit stack
  • Push nodes as we go left
  • Pop and process when we backtrack
  • Then go right
  • Binary Tree Preorder Traversal: Different traversal order
  • Binary Tree Postorder Traversal: Different traversal order
  • Validate BST: Uses inorder traversal
  • Kth Smallest Element in BST: Uses inorder traversal

Takeaways​

  • Stack simulates recursion for iterative traversal
  • Go left first to reach leftmost node
  • Process when popping from stack
  • Then go right to visit right subtree
  • O(n) time is optimal (must visit all nodes)