BST In-Order Without Recursion

Why iterative

Recursive in-order traversal is three lines: recurse(left); visit(node); recurse(right). Why would you ever write the iterative version?

• Stack overflow. An unbalanced BST can have height n. Python's default recursion limit is 1000. Real workloads with millions of entries need iteration.
• Streaming / pause-resume. "Give me one element at a time, pause indefinitely, resume on demand". Recursion can't do this without coroutine support. Iteration with an explicit stack does it naturally.
• Iterator API. A BSTIterator class that exposes next() and has_next() needs persistent state. The explicit stack is the state.
• Memory analysis. Iterative version's stack is exactly the path from root to the current node, at most O(h). Recursive version uses the same memory but it's hidden in the call stack, harder to reason about for memory-sensitive code.

The basic loop

def inorder(root):
    stack = []
    out = []
    curr = root
    while curr is not None or stack:
        # Walk all the way left, pushing each ancestor.
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        # The top of the stack is the next in-order node.
        curr = stack.pop()
        out.append(curr.val)
        # Now traverse its right subtree.
        curr = curr.right
    return out

The whole algorithm is the two-phase rhythm: walk left, pushing; pop, visit, go right. Repeat until both curr and the stack are empty.

The invariant: the stack contains the chain of ancestors of curr whose left subtrees have already been fully traversed but whose own values haven't yet been emitted. When we pop, we emit the closest such ancestor, which is guaranteed to be the next in sorted order.

A worked trace

BST: 4 → (2 → (1, 3), 5). Sorted order: 1, 2, 3, 4, 5.

start: curr=4, stack=[]
walk left: stack=[4], curr=2; stack=[4,2], curr=1; stack=[4,2,1], curr=None
pop 1, emit 1, curr=1.right=None
pop 2, emit 2, curr=2.right=3
walk left: stack=[4,3], curr=None
pop 3, emit 3, curr=3.right=None
pop 4, emit 4, curr=4.right=5
walk left: stack=[5], curr=None
pop 5, emit 5, curr=5.right=None
both empty → done

emitted: 1, 2, 3, 4, 5 ✓

Kth smallest, lazily

"Find the K-th smallest element in a BST." The recursive in-order would visit every node, then take the K-th. The iterative version stops the moment it has emitted K elements, saving (n − k) node visits when K is small.

def kth_smallest(root, k):
    stack = []
    curr = root
    while curr is not None or stack:
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right
    return -1                                # k larger than tree size

For balanced BSTs the saving is O(log n + k); for skewed ones it can be O(h + k). The point is that the algorithm is genuinely lazy: only the work needed to deliver the answer is performed.

The BST iterator

Encapsulate the same logic in a class. __init__ walks the leftmost path; next() pops, visits, and walks the right subtree's leftmost path; has_next() returns whether the stack is non-empty.

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node is not None:
            self.stack.append(node)
            node = node.left

    def has_next(self):
        return len(self.stack) > 0

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

The amortised analysis: each node is pushed exactly once and popped exactly once across the iterator's lifetime. Even though a single next() call can push many nodes when descending into a deep right subtree, the total pushes equal the total pops over n calls (both n). So next() is amortised O(1), with worst case O(h).

Variant: reverse in-order (descending)

Same algorithm, with left and right swapped. Walk all the way right pushing; pop; visit; walk into left. Useful for "Kth largest" and any descending-order traversal.

def reverse_inorder(root):
    stack, out, curr = [], [], root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.right
        curr = stack.pop()
        out.append(curr.val)
        curr = curr.left
    return out

Morris traversal with O(1) memory

For very memory-constrained traversal, Morris's algorithm achieves in-order with O(1) extra memory by temporarily threading the tree: link each predecessor's right pointer to the current node, then unlink on the way back. The traversal modifies the tree during the walk and restores it afterwards. Beautiful but rarely necessary; the explicit-stack version is the right interview answer.

When iterative beats recursive

• Trees deeper than the recursion limit. Iteration is the only safe option past ~1000 nodes in Python.
• You need an iterator API. Recursion can't pause; explicit stacks can.
• You're computing prefix-style answers (Kth smallest, "smallest greater than X"). Iteration stops as soon as the answer is found.
• You're in a memory-sensitive environment. Iterative explicit stack uses exactly O(h) memory; recursion uses the same plus per-frame overhead.

Where beginners go wrong

• Pushing the root, then walking left without pushing each ancestor. The stack must contain every ancestor whose left subtree is being explored, not just the root.
• Popping in the wrong moment. Pop happens after the left chain is exhausted. Popping inside the inner walk-left loop emits values out of order.
• Forgetting to advance to curr.right after popping. Without this, the loop spins on the popped node's null left pointer, doing nothing.
• Thinking the stack stores the result. The stack stores the path of ancestors; the result list (or generator yields, or iterator pops) is separate.

What to read next

Recursion as Structural Induction covers the recursive cousin of this concept. The Trees module covers heaps and balanced BSTs as related structures. Complexity Is a Contract explores the amortised analysis used in this iterator.