☕ DSA Java Articles

Topics › Binary Trees › Traversals

Iterative Inorder Traversal of Binary Tree

Easy TUF ID 2786 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its inorder traversal (left subtree, then the node, then the right subtree) without recursion. An empty tree gives an empty list.

Constraints: between 0 and 10^5 nodes, arbitrary 32-bit values, duplicates allowed. The tree may be a chain 10^5 levels deep, which rules out relying on the call stack.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

          1
        /   \
       2     3
        \   /
         4 5
          /
         6
root = [1, 2, 3, null, 4, 5, null, null, null, 6]
answer = [2, 4, 1, 6, 5, 3]     // 2 has no left subtree so it comes before 4; 3's left subtree (5, 6) precedes 3

Example 2

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13
root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
answer = [1, 3, 4, 6, 7, 8, 10, 13, 14]   // a binary search tree comes out sorted

The iterative inorder traversal is worth knowing well beyond this problem: it is the engine of the BST iterator, of “k-th smallest in a BST”, and of many “validate” and “recover” BST problems, all of which need to pause and resume an inorder walk.

Approach 1: Recursion (the reference)

Intuition. Inorder is defined recursively: inorder of the left subtree, the node, inorder of the right subtree. The iterative methods must reproduce exactly this output.

static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    inorder(root, out);
    return out;
}

private static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);                  // Left
    out.add(node.val);                        // Root
    inorder(node.right, out);                 // Right
}

Complexity. Time O(n), space O(h) on the call stack. On a chain h = n, which can overflow Java’s default stack.

Look at what a suspended frame means here. A frame waiting at inorder(node.left, out) represents a node whose left subtree is in progress and which still has to be output, followed by its right subtree. The iterative version keeps exactly those suspended nodes on an explicit stack.

Approach 2: The classic stack walk

Intuition. When we reach a node we cannot output it yet, because its whole left subtree comes first. So we postpone it by pushing it and step to its left child. When we step off the tree (cur == null), the node on top of the stack is the deepest postponed one, and its left subtree is now completely finished. Pop it, output it, and continue with its right subtree as if it were a fresh tree.

The invariant: the stack holds the nodes on the current path whose left subtree is in progress and which are not yet output, with the deepest on top.

Algorithm.

  1. Set cur = root, empty stack.
  2. While cur is not null or the stack is not empty:
    • If cur is not null: push it and move to cur.left.
    • Otherwise: pop a node into cur, append it, and move to cur.right.
static List<Integer> iterative(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);                  // postpone cur until its left subtree is finished
            cur = cur.left;
        } else {
            cur = stack.pop();                // left subtree of this node is finished
            out.add(cur.val);
            cur = cur.right;                  // continue with the right subtree
        }
    }
    return out;
}

Dry run on Example 1. The stack is written bottom to top.

Step cur Action Stack after Output so far
1 1 push, go left [1]  
2 2 push, go left [1, 2]  
3 null pop 2, output, go right to 4 [1] 2
4 4 push, go left [1, 4] 2
5 null pop 4, output, go right (null) [1] 2 4
6 null pop 1, output, go right to 3 [] 2 4 1
7 3 push, go left [3] 2 4 1
8 5 push, go left [3, 5] 2 4 1
9 6 push, go left [3, 5, 6] 2 4 1
10 null pop 6, output, go right (null) [3, 5] 2 4 1 6
11 null pop 5, output, go right (null) [3] 2 4 1 6 5
12 null pop 3, output, go right (null) [] 2 4 1 6 5 3

After step 6 the stack is empty but cur is node 3, so the loop must continue. That is why the condition is cur != null || !stack.isEmpty(), and why neither half alone is enough.

Complexity. Time O(n): each node is pushed once and popped once, and every iteration does one of the two. Space O(h): the stack is a subset of one root-to-node path.

Approach 3: Simulate the recursion with flagged entries

Intuition. There is a mechanical way to turn any of the three depth-first traversals into an iterative one, useful when you do not remember the specialised trick. Think of each node as needing two kinds of attention: first it must be expanded (schedule its left subtree, itself and its right subtree), and later it must be emitted. Put both kinds of task on one stack, marking each entry with a flag. Because the stack is last-in-first-out, push the three tasks in reverse of the order you want them done.

For inorder the wanted order is left subtree, the node, right subtree, so we push the right child, then the node marked ready, then the left child. A ready entry is emitted when popped; at that moment everything pushed above it, which is the whole left subtree, has already been processed.

The Java record keeps the flag and the node together.

record Entry(TreeNode node, boolean ready) {}

Algorithm.

  1. If the root is null, return an empty list. Otherwise push (root, false).
  2. While the stack is not empty: pop an entry.
    • If it is ready, append its node.
    • Otherwise push (right, false) if a right child exists, then (node, true), then (left, false) if a left child exists.
static List<Integer> iterativeWithFlags(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<Entry> stack = new ArrayDeque<>();
    stack.push(new Entry(root, false));
    while (!stack.isEmpty()) {
        Entry e = stack.pop();
        TreeNode node = e.node();
        if (e.ready()) {
            out.add(node.val);                // everything to its left has already been emitted
            continue;
        }
        // push in reverse of the wanted order, so they pop as Left, Node, Right
        if (node.right != null) stack.push(new Entry(node.right, false));
        stack.push(new Entry(node, true));
        if (node.left != null) stack.push(new Entry(node.left, false));
    }
    return out;
}

Changing only the push order gives the other traversals. For preorder push right, left, then the ready node, so the node is popped first. For postorder push the ready node first, then right, then left, so the node is popped after both subtrees. That makes this template a dependable fallback in an interview.

Complexity. Time O(n): each node is pushed twice (once to expand, once ready) and popped twice. Space O(h): at any time the stack holds, for each node on the current path, at most its ready entry and its pending right child.

Edge cases and pitfalls