Binary Tree In-Order Traversal, in depth: the recursive rule, the explicit-stack loop traced step by step, lazy iterators, successors and deep-tree bugs

The rule, and why it sorts a BST

Write the walk as a rule applied at every node: finish everything in the left subtree, then emit the node, then do everything in the right subtree. The three depth-first orders differ only in where the emit goes: pre-order emits before both subtrees, post-order after both, and in-order between them. That position is what gives in-order its special property on a BST. The BST invariant says every key in a node's left subtree is smaller and every key in its right subtree is larger. In-order emits all the smaller keys, then the node, then all the larger keys, and the same argument holds inside each subtree, so by induction on tree size the whole output is ascending.

The converse is also useful: if an in-order walk of a binary tree is strictly increasing, the tree is a valid BST with distinct keys. That gives one clean validation method: walk in order and check each key against the previous one.

The worked tree used throughout is the BST built by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13. Its in-order sequence is 1 3 4 6 7 8 10 13 14.

The recursive walk

The recursive version reads exactly like the definition. Use a callback or a generator rather than building a list inside the recursion when the caller may want to stop early.

class Node:
    __slots__ = ("val", "left", "right")
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder_recursive(node, visit):
    if node is None:
        return
    inorder_recursive(node.left, visit)
    visit(node.val)
    inorder_recursive(node.right, visit)

out = []
inorder_recursive(root, out.append)   # out == [1, 3, 4, 6, 7, 8, 10, 13, 14]

Cost: every node is entered once and every None child is checked once, so time is O(n). The call stack holds one frame per node on the current root-to-node path, so extra space is O(h), where h is the height. For a balanced tree h is about log2 n; for a tree built by inserting already-sorted keys into a plain BST, every node has only a right child and h equals n. That last case is where the recursive version fails.

The explicit-stack loop

The explicit-stack version simulates the call stack. The insight is that a recursive call to the left child is the only work that happens before a node's visit, so you can do all of those calls at once: from the current node, walk left as far as possible, pushing each node. The top of the stack is then the smallest unvisited node. Pop it, visit it, and move to its right child, which starts the same process again for the right subtree.

def inorder_iterative(root):
    out, stack, cur = [], [], root
    while cur is not None or stack:
        while cur is not None:          # run down the left spine
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()               # smallest unvisited node
        out.append(cur.val)             # visit
        cur = cur.right                 # then handle its right subtree
    return out

The loop invariant is worth saying out loud, because it is how you convince yourself the code is right: the stack holds, from bottom to top, the ancestors of cur whose visit is still pending, and every one of them is reached by a left edge from the one below. Each such node is visited only after its entire left subtree, which is exactly the in-order rule. The outer condition must include cur is not None: after popping the root of a tree, the stack can be empty while the root's right subtree has not been touched yet.

Tracing the stack by hand

Here is the loop run by hand on the worked tree. Stack contents are listed bottom to top.

Two things stand out. First, after step 7 the stack is empty while the walk is only half done, which is the case the cur is not None clause covers. Second, each node is pushed and popped exactly once: O(n) time, peak stack bounded by the height.

Lazy iterators, merges and range queries

Most real uses do not want the whole list. A k-th smallest query wants to stop after k keys; a merge of two BSTs wants to advance two walks in step; a paginated API wants the next 50 keys after a cursor. The explicit-stack loop splits naturally into a lazy iterator: the constructor runs down the left spine, and each next pops one node, then runs down the left spine of that node's right child.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

final class InorderIterator {
    private final Deque<Node> stack = new ArrayDeque<>();

    InorderIterator(Node root) { pushLeft(root); }

    boolean hasNext() { return !stack.isEmpty(); }

    int next() {
        if (stack.isEmpty()) throw new NoSuchElementException();
        Node n = stack.pop();
        pushLeft(n.right);
        return n.val;
    }

    private void pushLeft(Node n) {
        for (; n != null; n = n.left) stack.push(n);
    }
}

A single next can push up to h nodes, but across a whole walk every node is pushed once, so the amortised cost per call is O(1) and memory is O(h). In Python the same thing is a generator, which is usually the cleanest choice:

def inorder_iter(root):
    stack, cur = [], root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        yield cur.val
        cur = cur.right

Range queries prune the walk instead of filtering its output. When looking for keys in [lo, hi], skip a node's left subtree if the node's key is below lo, because everything there is smaller still, and stop entirely once a visited key exceeds hi. On a balanced tree that costs O(h + k) for k results rather than O(n).

Successors with parent pointers

Some trees store a parent pointer on every node: many red-black tree implementations do, and so do tree-backed sorted maps that need to step from an arbitrary node. With parent pointers you can find the in-order successor of any node without a stack. If the node has a right child, the successor is the leftmost node of the right subtree. Otherwise climb until you arrive at an ancestor from its left side; that ancestor is the successor. If you reach the root from the right, there is none.

def successor(n):
    if n.right is not None:
        n = n.right
        while n.left is not None:
            n = n.left
        return n
    while n.parent is not None and n is n.parent.right:
        n = n.parent
    return n.parent          # None when n was the maximum

A full walk by repeated successor calls touches each edge at most twice, so it is still O(n) in total with O(1) extra space, and unlike Morris it never modifies the tree. The cost is one extra pointer per node and the discipline of keeping parent links correct during rotations and deletes. Morris traversal gets O(1) space without parent pointers by temporarily threading the tree; see the Morris traversal deep dive for how it works and why an early exit can leave threads behind.

Where in-order earns its keep

• BST validation. Walk in order and require each key to be greater than the previous one. Keep the previous key in a variable, not a list. The BST validation article compares this with the bounds-passing method and covers duplicate keys.
• K-th smallest. Count visits and stop at k: O(h + k) with the iterator. For repeated queries on a changing tree, augment nodes with subtree sizes instead; the k-th smallest article walks through both.
• Tree reconstruction. In-order plus pre-order (or post-order) identifies a tree with distinct keys uniquely; see building a tree from two traversals.
• Expression trees. In-order on an expression tree gives infix notation, but only if you add parentheses around each internal node's output; without them, (a + b) * c and a + (b * c) print the same.

Failure modes

These are the bugs that actually turn up in code review and in production.

• Recursion depth on skewed trees. CPython's default recursion limit is 1000 (sys.getrecursionlimit()), so the recursive walk of a 5,000-node right-leaning tree raises RecursionError. Raising the limit just moves the failure to a C-stack crash. In Java the equivalent is StackOverflowError; how many frames fit depends on the thread stack size and frame size, so do not rely on a number. If the tree can be skewed, use the explicit stack.
• Wrong loop condition. Writing while stack: after pushing only the root stops as soon as the stack empties, which on the worked tree happens right after visiting 8, so 10, 13 and 14 are silently dropped. Tests on small balanced trees often miss it. Test a root with only a right subtree.
• Mutating the tree during iteration. A lazy iterator holds references to nodes on its stack. Deleting one of them, or rotating the tree to rebalance, leaves the iterator pointing into a shape that no longer exists. Either snapshot, fail fast with a modification counter as Java's collections do, or restart from the last returned key with a fresh descent.
• Stopping Morris early. An early return from a Morris walk leaves temporary right-pointer threads in place, corrupting the tree for the next reader. If you need early exit, use the stack iterator.
• Duplicate keys. If the tree allows duplicates on one side, in-order output is non-decreasing rather than strictly increasing; a validator that demands strict order will reject a correct tree, and one that accepts equal keys on both sides will accept a broken one.

Trade-offs

Testing traversal code

Test traversal code against a property rather than hand-written expected lists. Build a BST from random distinct keys, walk it with each implementation, and assert that every output equals sorted(keys). Include an empty tree, a single node, a fully left-skewed tree, a fully right-skewed tree and a tree of a few thousand nodes inserted in sorted order, which catches both the loop-condition bug and the recursion limit.

import random

def insert(root, v):
    if root is None:
        return Node(v)
    cur = root
    while True:
        if v < cur.val:
            if cur.left is None: cur.left = Node(v); break
            cur = cur.left
        else:
            if cur.right is None: cur.right = Node(v); break
            cur = cur.right
    return root

for trial in range(500):
    keys = random.sample(range(10_000), random.randint(0, 200))
    root = None
    for k in keys:
        root = insert(root, k)
    assert inorder_iterative(root) == sorted(keys)
    assert list(inorder_iter(root)) == sorted(keys)

skewed = None
for k in range(5_000):                  # sorted inserts: height 5,000
    skewed = insert(skewed, k)
assert inorder_iterative(skewed) == list(range(5_000))

What to do next

1. Write the explicit-stack loop from memory, then trace it by hand on the worked tree and check that your stack matches the table above at each step.
2. Turn it into a generator or iterator class, and use it to answer a k-th smallest query that stops early.
3. Add the property test with random trees plus a 5,000-node sorted-insert tree; run it against any recursive traversal in your codebase to see whether it survives.
4. Search your code for recursive tree walks over data you do not control, and replace them with the stack version or bound the input height.
5. If your trees keep parent pointers, implement successor and use it for cursor-based pagination.
6. Read the iterative DFS article to see how the same explicit-stack idea generalises to graphs, finish times and cycle detection.