Introduction

An in-order iterator lets you traverse a binary tree one element at a time without writing recursive traversal code at every call site. The usual iterative solution stores the path to the next node in a stack, giving you ordered traversal with predictable space usage.

How in-order traversal works

In-order traversal visits nodes in this sequence:

1. left subtree
2. current node
3. right subtree

For a binary search tree, that produces values in sorted order. The challenge for an iterator is preserving just enough state to resume where the previous next() call stopped.

A stack-based iterator

The standard pattern is:

• push the entire left chain from the current root,
• pop the top node when next() is called,
• then push the left chain of that node's right child.

Here is a complete Python implementation:

1class TreeNode:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8class InOrderIterator:
9    def __init__(self, root):
10        self.stack = []
11        self._push_left(root)
12
13    def _push_left(self, node):
14        while node is not None:
15            self.stack.append(node)
16            node = node.left
17
18    def __iter__(self):
19        return self
20
21    def __next__(self):
22        if not self.stack:
23            raise StopIteration
24
25        node = self.stack.pop()
26        self._push_left(node.right)
27        return node.value

The helper method _push_left is the key. It keeps the next smallest unvisited node on top of the stack.

Example usage

Build a small tree:

1root = TreeNode(
2    4,
3    left=TreeNode(2, TreeNode(1), TreeNode(3)),
4    right=TreeNode(6, TreeNode(5), TreeNode(7)),
5)
6
7for value in InOrderIterator(root):
8    print(value)

Output:

11
22
33
44
55
66
77

That ordering comes from always exhausting the left side before visiting a node and then moving to its right subtree.

Why the complexity is efficient

Each node is pushed onto the stack once and popped once, so the total work is linear in the number of nodes. A single next() call is amortized O(1), while the stack uses O(h) space where h is the tree height.

That is a good tradeoff because the iterator does not need to store all node values in advance. It yields them lazily as requested.

Returning nodes instead of values

Sometimes the caller needs the whole node instead of just the value. In that case, return node from __next__ instead of node.value. The traversal algorithm does not change.

You can also add a has_next() helper in languages that prefer it:

def has_next(self):
    return bool(self.stack)

Python's iterator protocol does not require that method, but Java and C++ style iterators often expose an equivalent check.

Common Pitfalls

The most common bug is forgetting to push the left chain of the popped node's right child. If you skip that step, the iterator visits the root of the right subtree but misses everything below its left branch.

Another issue is assuming next() is worst-case constant time. A single call may walk down several left children, but across the entire traversal each node is still processed only once, which is why the amortized cost stays low.

Be careful when modifying the tree during iteration. If nodes are inserted or removed while the iterator is active, the stack may no longer represent a consistent traversal state.

Finally, do not replace the stack with recursion if the goal is a reusable iterator. Recursion is fine for one-off traversal, but an iterator needs explicit state between calls.

Summary

• An in-order iterator uses a stack to remember the path to the next node.
• The core rule is: pop one node, then push the left chain of its right child.
• The iterator yields sorted values for a binary search tree.
• Space usage is O(h) and total traversal time is O(n).
• Explicit iterator state is what makes lazy, step-by-step traversal possible.