L10: Iterative Inorder Traversal in Binary Tree (C++ | Java | Stack)

Inorder traversal visits a binary tree in the specific order of Left -> Root -> Right. While recursive implementations naturally rely on the system's function call stack, interviews often require an iterative solution to avoid recursion overhead and stack overflow risks. By explicitly managing our own Stack data structure, we can replicate the exact execution trace of recursion iteratively.

1. Why Do We Need Iterative Inorder Traversal?

• Recursion Limitations: Recursive tree traversals utilize the underlying call stack. For deeply skewed trees, this can easily lead to a StackOverflowError.
• Interview Constraints: Technical interviewers frequently forbid recursion for tree traversals to test your understanding of data structures, pointer manipulation, and explicit state management.
• Explicit Control: Using an explicit Stack allows us to pause, store, and resume traversal states precisely where we need them.

2. Core Mental Model: Replicating the Recursive Call Stack

In a recursive inorder traversal, the computer implicitly tracks parent nodes while diving deep into the left subtree.

Real-Life Analogy: The Stack of Unfinished Plates

Imagine inspecting a multi-level shelving unit where you must always check the leftmost compartment first:

1. You walk down as far left as possible, placing each encountered parent node onto a pile (your stack) so you remember how to get back to them.
2. When you hit a dead end (null left child), you pop the last placed item from your pile, process (print) it, and then shift your attention to its right child.
3. This mirrors the exact LIFO (Last-In, First-Out) behavior of recursion.

3. Understanding the Inorder Sequence: Left -> Root -> Right

Consider the following binary tree structure:

        1
       / \
      2   3
     /   / 
    4   5   
       / \
      6   7

Following the Left -> Root -> Right rule:

1. Dive left as far as possible: reach 4. Since 4 has no left child, print 4.
2. Return to its root: print 2.
3. Explore 2's right subtree: 5 -> 6 (left of 5), print 6, then print 5, then 7 (right of 5), print 7.
4. Return to root 1, print 1.
5. Visit right subtree of 1: 3, print 3.

Complete Inorder Output: 4 -> 2 -> 6 -> 5 -> 7 -> 1 -> 3

4. Step-by-Step Iterative Algorithm Design

To implement this iteratively, we maintain two main components:

1. A Stack of tree nodes to keep track of nodes we've deferred.
2. A current pointer initialized to the root of the tree.

The Loop Condition

We continue our while loop as long as current is not null OR the stack is not empty.

Inside the loop, we handle two distinct states:

• Case A (current != null): We push the current node onto the stack and move strictly to its left child (current = current.left).
• Case B (current == null): We have hit a dead-end on the left. We pop the top element from the stack, print/store its value, and shift our focus to its right child (current = current.right).

5. Dry Run Walkthrough with Example Tree

Let's trace our algorithm on our sample tree starting at node 1:

Initial State:
stack = []
current = 1
inorder = []

1. Iteration 1: current is 1 (not null). Push 1 to stack. Move left.
   • stack = [1]
   • current = 2
2. Iteration 2: current is 2 (not null). Push 2 to stack. Move left.
   • stack = [1, 2]
   • current = 4
3. Iteration 3: current is 4 (not null). Push 4 to stack. Move left.
   • stack = [1, 2, 4]
   • current = null
4. Iteration 4: current is null. Go to Case B. Pop 4 from stack. Print 4. Move to 4's right (null).
   • stack = [1, 2]
   • inorder = [4]
   • current = null
5. Iteration 5: current is null. Pop 2 from stack. Print 2. Move to 2's right (5).
   • stack = [1]
   • inorder = [4, 2]
   • current = 5
6. Iteration 6: current is 5 (not null). Push 5 to stack. Move left (6).
   • stack = [1, 5]
   • current = 6
7. Iteration 7: current is 6 (not null). Push 6 to stack. Move left (null).
   • stack = [1, 5, 6]
   • current = null
8. Iteration 8: current is null. Pop 6. Print 6. Move to 6's right (null).
   • stack = [1, 5]
   • inorder = [4, 2, 6]
   • current = null
9. Iteration 9: current is null. Pop 5. Print 5. Move to 5's right (7).
   • stack = [1]
   • inorder = [4, 2, 6, 5]
   • current = 7

(Process continues similarly for node 7, 1, and 3 until the stack is empty and current is null).

6. Complete Code Implementation (C++ and Java)

Below are the complete, production-ready implementations mirroring the iterative approach demonstrated in the lecture.

C++ Implementation

#include <bits/stdc++.h>
using:// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> inorder;
        stack<TreeNode*> st;
        TreeNode* current = root;

        while (current != nullptr || !st.empty()) {
            // Reach the left-most node of the current node
            while (current != nullptr) {
                st.push(current);
                current = current->left;
            }

            // Current is null at this point, so pop from stack
            current = st.top();
            st.pop();
            
            // Add to traversal result (visit root)
            inorder.push_back(current->val);

            // Move to the right subtree
            current = current->right;
        }

        return inorder;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        TreeNode current = root;

        while (current != null || !st.empty()) {
            // Push all left nodes onto the stack
            while (current != null) {
                st.push(current);
                current = current.left;
            }

            // Pop the top element, process it, and shift to right child
            current = st.pop();
            inorder.add(current.val);
            current = current.right;
        }

        return inorder;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Iterative Alternative: Iterative inorder traversal eliminates system recursion stack overhead, preventing potential stack overflow errors on deep trees.
• The Stack Data Structure: We explicitly use a LIFO (Last-In, First-Out) stack to track parent nodes while descending down left subtrees.
• Two-Phase Loop Logic:
  1. Dive Left: Push nodes to the stack while moving left.
  2. Process and Shift Right: When current hits null, pop from the stack, record the node's value, and switch to its right child.
• Time Complexity is $O(N)$: Each node is visited and processed exactly once.
• Space Complexity is $O(H)$ or $O(N)$: Dependent on tree shape, bounded by tree height $H$ for balanced trees and total nodes $N$ for skewed trees.