Iterative in-order traversal of a binary tree

You're in a technical interview at Amazon, and the interviewer draws a binary tree on the whiteboard. "Can you traverse this tree in-order, but without using recursion?" This problem, also known as "Binary Tree Inorder Traversal" on platforms like LeetCode, is a staple of coding interviews because it tests whether you can translate recursive thinking into explicit stack operations. It shows up regularly at companies like Amazon, Oracle, and across the industry.

TL;DR

Use a stack and an iterator pointer to simulate the recursive call stack. Push all left children onto the stack first, then pop a node, add its value to the output, and move to its right child. The outer loop continues while there are nodes left to process (either the iterator is non-null or the stack has entries). This runs in O(n) time and O(n) space.

Why This Problem Matters

In-order traversal is one of the three fundamental depth-first traversal patterns for binary trees (alongside pre-order and post-order). For binary search trees, in-order traversal produces values in sorted order, making it critical for problems like finding the kth smallest element or validating BST properties. The iterative version specifically tests your ability to manage state with a stack, which is a skill that transfers to dozens of other tree and graph problems.

Binary Trees and Traversal Orders

Before we dig into the algorithm, let's review the three standard depth-first traversal orders on the same tree:

In-order gets its name from the fact that the root is visited "in" the middle, between the left and right subtrees. For our example tree, we visit node 2 (left subtree) first, then node 1 (root), then nodes 4, 3, 5 (right subtree processed in-order).

Understanding the Problem

Given: The root of a binary tree Task: Return a list of node values in in-order (left, root, right) using iteration, not recursion Return: A list of integers representing the visited node values

Here's the example from the problem:

inOrder(root) -> [2, 1, 4, 3, 5]

The traversal visits node 2 first (leftmost), then backtracks to node 1, then processes the right subtree rooted at 3 in-order: 4, 3, 5.

Edge Cases

1. Empty tree (null root): Return an empty list
2. Single node: Return a list with just that node's value
3. Left-skewed tree: All nodes on the left side, visited bottom-up
4. Right-skewed tree: Root visited first, then each right child in sequence

From Recursion to Iteration

The recursive version of in-order traversal is short and elegant:

void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);      // Process left subtree
    visit(node);              // Process current node
    inOrder(node.right);     // Process right subtree
}

But when an interviewer says "do it iteratively," you need to manage the traversal state yourself. The recursive call stack remembers which nodes you still need to return to after processing a left subtree. To replicate that behavior, you use an explicit stack.

The insight is this: as you descend leftward, you push each node onto the stack, deferring it for later. When you reach a null left child, you pop the most recent node, visit it, and then move to its right child. The outer loop keeps going as long as there is either a node to descend into or a deferred node on the stack.

The Algorithm Step by Step

Let's trace through the example tree to see exactly how the stack and output evolve:

The highlighted states are the "pop" steps where a node's value is added to the output. Notice the pattern: every node is pushed exactly once and popped exactly once. The inner while loop handles the "go left" phase, and the pop-then-go-right sequence handles the "visit and move on" phase.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {
  public List<Integer> inOrder(TreeNode root) {
    // Create an output list to collect visited node values
    List<Integer> out = new ArrayList<>();

    // Use a Deque as a stack to track deferred nodes
    Deque<TreeNode> stack = new LinkedList<>();

    // Iterator pointer starts at the root
    TreeNode iterator = root;

    // Continue while there are nodes to process
    while (iterator != null || !stack.isEmpty()) {
      // Push all left children onto the stack
      while (iterator != null) {
        stack.push(iterator);
        iterator = iterator.left;
      }

      // Pop the top node, visit it, then move to its right child
      iterator = stack.pop();
      out.add(iterator.data);
      iterator = iterator.right;
    }

    return out;
  }
}

Let's walk through the key sections:

1. The outer loop condition iterator != null || !stack.isEmpty() covers two scenarios: either we have a node to descend into (iterator is non-null), or we have deferred nodes on the stack waiting to be visited.

2. The inner loop while (iterator != null) descends as far left as possible, pushing each node onto the stack. This mirrors the recursive inOrder(node.left) call.

3. The pop-and-visit section corresponds to the visit(node) step in the recursive version. After visiting, we set the iterator to the right child, which mirrors inOrder(node.right).

Animated Traversal

Watch the traversal unfold step by step on our example tree:

Complexity Analysis

Time Complexity: O(n)

Every node in the tree is pushed onto the stack exactly once and popped exactly once. Each push and pop is an O(1) operation. Therefore, the total work is proportional to the number of nodes.

Space Complexity: O(n)

The stack can hold at most O(h) nodes at any time, where h is the height of the tree. For a balanced tree, h = O(log n), so the space is O(log n). For a skewed tree (all nodes on one side), h = n, giving O(n) worst-case space. The output list always uses O(n) space.

Common Pitfalls

1. Using only the stack in the loop condition: Writing while (!stack.isEmpty()) misses the initial case where the stack is empty but the iterator points to the root. You need iterator != null || !stack.isEmpty().

2. Forgetting to move right after popping: If you skip iterator = iterator.right, you'll re-process the same left paths forever, causing an infinite loop.

3. Confusing in-order with pre-order: In pre-order, you add the node's value before pushing and descending left. In in-order, you add it after popping. This subtle timing difference changes the entire output.

4. Processing in the inner loop: Adding node values inside the inner while loop produces pre-order output, not in-order. The visit must happen after the inner loop exits.

Interview Tips

When this comes up in an interview:

1. Clarify the traversal order: In-order means left, root, right. Confirm with the interviewer.

2. Mention the recursive version first: Show you understand the concept, then explain how you'll convert it to iterative. This demonstrates thought process.

3. Draw the stack state: Sketch a few iterations showing what's on the stack and what's in the output. This catches logic errors before you write code.

4. Know the BST connection: If the interviewer asks follow-up questions, mention that in-order traversal on a BST yields sorted output. This opens the door to problems like kth smallest element or BST validation.

5. Mention Morris traversal: If asked about O(1) space, briefly describe Morris traversal, which threads the tree temporarily. You probably won't need to implement it, but awareness shows depth.

Key Takeaways

• The iterative in-order pattern uses two nested loops: an outer loop checking iterator != null || !stack.isEmpty(), and an inner loop pushing left children. Popping happens between the inner loop exit and the right-child assignment.
• Every node is pushed and popped exactly once, giving O(n) time. Stack depth matches tree height, so space ranges from O(log n) for balanced trees to O(n) for skewed trees.
• In-order traversal on a BST produces sorted output. This property underlies kth smallest, BST validation, and BST-to-sorted-array conversions.
• The critical difference from pre-order is timing: in pre-order you visit before pushing left children, in in-order you visit after popping from the stack.
• If space is a concern, Morris traversal achieves O(1) space by temporarily threading the tree, but the stack-based approach is the standard interview answer.

Solutions in Other Languages

Python

from collections import deque
from typing import List

class Solution:
    def in_order(self, root):
        out = list()
        stack = deque()
        iterator = root
        while iterator is not None or len(stack) > 0:
            while iterator is not None:
                stack.append(iterator)
                iterator = iterator.left
            iterator = stack.pop()
            out.append(iterator.data)
            iterator = iterator.right
        return out

JavaScript

class Solution {
  inOrder(root) {
    const out = [];
    const stack = [];
    let iterator = root;
    while (iterator !== null || stack.length > 0) {
      while (iterator !== null) {
        stack.push(iterator);
        iterator = iterator.left;
      }
      iterator = stack.pop();
      out.push(iterator.data);
      iterator = iterator.right;
    }
    return out;
  }
}

TypeScript

class Solution {
  inOrder(root: TreeNode | null): number[] {
    const out: number[] = [];
    const stack: TreeNode[] = [];
    let iterator: TreeNode | null = root;
    while (iterator !== null || stack.length > 0) {
      while (iterator !== null) {
        stack.push(iterator);
        iterator = iterator.left;
      }
      iterator = stack.pop()!;
      out.push(iterator.data);
      iterator = iterator.right;
    }
    return out;
  }
}

C++

#include <stack>
#include <vector>

class Solution {
public:
  std::vector<int> inOrder(TreeNode *root) {
    std::vector<int> out;
    std::stack<TreeNode *> stack;
    TreeNode *iterator = root;
    while (iterator != nullptr || !stack.empty()) {
      while (iterator != nullptr) {
        stack.push(iterator);
        iterator = iterator->left;
      }
      iterator = stack.top();
      stack.pop();
      out.push_back(iterator->data);
      iterator = iterator->right;
    }
    return out;
  }
};

Go

func (s *Solution) InOrder(root *TreeNode) []int {
    var out []int
    stack := NewStack()
    iterator := root
    for iterator != nil || !stack.IsEmpty() {
        for iterator != nil {
            stack.Push(iterator)
            iterator = iterator.Left
        }
        iterator = stack.Pop().(*TreeNode)
        out = append(out, iterator.Data)
        iterator = iterator.Right
    }
    return out
}

Scala

import scala.collection.mutable

class Solution {
  def inOrder(root: TreeNode): List[Int] = {
    val out = mutable.ArrayBuffer[Int]()
    val stack = mutable.Stack[TreeNode]()
    var iterator = root
    while (iterator != null || stack.nonEmpty) {
      while (iterator != null) {
        stack.push(iterator)
        iterator = iterator.left
      }
      iterator = stack.pop
      out.append(iterator.data)
      iterator = iterator.right
    }
    out.toList
  }
}

Kotlin

import java.util.*

class Solution {
  fun inOrder(root: TreeNode?): List<Int> {
    val out = mutableListOf<Int>()
    val stack = LinkedList<TreeNode?>()
    var iterator = root
    while (iterator != null || !stack.isEmpty()) {
      while (iterator != null) {
        stack.push(iterator)
        iterator = iterator.left
      }
      iterator = stack.pop()
      out.add(iterator!!.data)
      iterator = iterator.right
    }
    return out
  }
}

Swift

class Solution {
    func inOrder(_ root: TreeNode?) -> [Int] {
        var output = [Int]()
        var stack = [TreeNode]()
        var iterator = root
        while iterator != nil || !stack.isEmpty {
            while iterator != nil {
                stack.append(iterator!)
                iterator = iterator!.left
            }
            iterator = stack.removeLast()
            output.append(iterator!.data)
            iterator = iterator!.right
        }
        return output
    }
}

Rust

impl Solution {
    pub fn in_order(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        let mut out: Vec<i32> = Vec::new();
        let mut stack: Vec<&TreeNode> = Vec::new();
        let mut iterator = root.as_deref();
        while iterator.is_some() || !stack.is_empty() {
            while let Some(node) = iterator {
                stack.push(node);
                iterator = node.left.as_deref();
            }
            let node = stack.pop().unwrap();
            out.push(node.data);
            iterator = node.right.as_deref();
        }
        out
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public List<int> InOrder(TreeNode? root) {
        var result = new List<int>();
        var stack = new Stack<TreeNode>();
        var iterator = root;
        while (iterator != null || stack.Count > 0) {
            while (iterator != null) {
                stack.Push(iterator);
                iterator = iterator.left;
            }
            iterator = stack.Pop();
            result.Add(iterator.data);
            iterator = iterator.right;
        }
        return result;
    }
}

Dart

class Solution {
  List<int> inOrder(TreeNode? root) {
    List<int> out = [];
    List<TreeNode> stack = [];
    TreeNode? iterator = root;
    while (iterator != null || stack.isNotEmpty) {
      while (iterator != null) {
        stack.add(iterator);
        iterator = iterator.left;
      }
      iterator = stack.removeLast();
      out.add(iterator.data);
      iterator = iterator.right;
    }
    return out;
  }
}

PHP

class Solution {
    public function inOrder(?TreeNode $root): array {
        $out = [];
        $stack = [];
        $iterator = $root;
        while ($iterator !== null || !empty($stack)) {
            while ($iterator !== null) {
                $stack[] = $iterator;
                $iterator = $iterator->left;
            }
            $iterator = array_pop($stack);
            $out[] = $iterator->data;
            $iterator = $iterator->right;
        }
        return $out;
    }
}

Ruby

class Solution
  def in_order(root)
    out = []
    stack = []
    iterator = root
    while iterator || !stack.empty?
      while iterator
        stack.push(iterator)
        iterator = iterator.left
      end
      iterator = stack.pop
      out << iterator.data
      iterator = iterator.right
    end
    out
  end
end

Practice Makes Perfect

Iterative in-order traversal is one of the building blocks for more advanced tree problems. Once you're comfortable with this pattern, try these related challenges:

• Iterative pre-order traversal (similar pattern, different visit timing)
• Kth smallest element in a BST (modify in-order to stop early)
• Validate a binary search tree (use in-order and check sorted order)
• Binary tree level-order traversal (switch from stack to queue)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Practicing iterative tree traversal until it becomes second nature will pay dividends across your entire interview preparation.