Iterative Inorder Traversal of a Binary Tree

1. Introduction

Inorder traversal of a binary tree follows this order:

Left Subtree → Root → Right Subtree

This is typically implemented using recursion, but recursion uses the call stack implicitly. In iterative traversal, we simulate that behavior explicitly using a stack.

2. Why Use Iterative Traversal?

While recursive traversal is elegant, iterative traversal is sometimes preferred because:

It avoids stack overflow for deep trees.
It gives more control over the flow.
It can be more memory-efficient in some contexts.

3. How Iterative Inorder Traversal Works

We simulate the recursive behavior using a stack:

Traverse to the leftmost node, pushing each node on the stack.
Once we reach null, we pop from the stack, process the node, and move to its right child.
Repeat the process until both stack is empty and current node is null.

4. Tree Structure Example

Consider this tree:

Expected Inorder Output: 4 2 5 1 3

5. Java Implementation

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class IterativeInorderTraversal {

    public void inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // 1. Reach the leftmost node of the current node
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // 2. Current must be null at this point, so we pop from stack
            current = stack.pop();

            // 3. Visit the node
            System.out.print(current.val + " ");

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

    public static void main(String[] args) {
        // Construct the tree:
        //         1
        //        / \
        //       2   3
        //      / \
        //     4   5

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        IterativeInorderTraversal tree = new IterativeInorderTraversal();
        System.out.println("Inorder Traversal (Iterative):");
        tree.inorderTraversal(root);  // Output: 4 2 5 1 3
    }
}

6. Visual Stack Simulation

Initial tree:
        1
       / \
      2   3
     / \
    4   5

Stack Actions:

Push 1
Push 2
Push 4
Visit 4 → Print
Pop 2 → Print
Push 5
Visit 5 → Print
Pop 1 → Print
Push 3
Visit 3 → Print

7. Time and Space Complexity

Time Complexity:

Every node is visited once → O(n)

Space Complexity:

Stack holds up to O(h) nodes at a time, where h is the height of the tree.
- Best case (balanced tree): O(log n)
- Worst case (skewed tree): O(n)

9. When to Use Iterative Inorder

In systems where stack overflows are a concern.
When you need fine-grained control over traversal (pause, resume, parallelism).
For implementing iterators in data structures like BSTIterator.
When building interactive tree visualizations or event-based systems.