In-order traversal

The problem it solves

A tree holds your data; now you need it out — every node, exactly once, in a defined order. Traversal is that extraction, and the specific order matters enormously: in-order (left, node, right) applied to a binary search tree emits the values in sorted order, which is simultaneously a free sorting pass, the standard way to validate a BST, the engine behind “k-th smallest element”, and the reason range queries on tree-backed maps come out ordered.

The traversal family is one skeleton with three timings — pre-order emits on arrival (serialize/copy a tree), post-order emits on departure (delete a tree, compute sizes bottom-up), in-order emits in between — and interviews treat fluency across all three as a baseline. This page focuses on in-order because it has the theorem attached.

The intuition — and where it breaks down

Reading a family bookshelf organized by a strict rule: everything shelved left of a divider is alphabetically earlier than the divider’s own label, everything right is later — recursively, dividers within dividers. To read the whole shelf in alphabetical order, the procedure writes itself: read the entire left section first (it’s all earlier), then the divider itself, then the right section. Apply the same procedure inside each section. You never plan, sort, or look ahead — the structure already encodes the order, and the traversal merely walks it out.

The subtle move — the one the prediction prompts drill — is that “read the left section first” recurses: entering any subtree, the first thing emitted is not its root but its leftmost descendant, reached by sliding down left pointers all the way. The root of a subtree, no matter how prominent, waits until its entire left flank has spoken. Emitting the root on arrival is a different algorithm (pre-order) and a different, unsorted output.

Where the analogy breaks: bookshelves are finite and visible — you can see the leftmost book. The recursion cannot; it discovers the leftmost by walking, and it needs a way back up. That way back is the call stack, and it is doing real work: at every moment it holds exactly the chain of ancestors whose right sections remain unread. The analogy hides the bookkeeping; the visualization’s call-frame panel puts it back.

Loading…

A walkthrough you can check

Tree built from 5, 3, 8, 1, 4 (root 5; 3 left of it with children 1, 4; 8 right).

1. Enter 5 — don’t emit. Go left.
2. Enter 3 — don’t emit. Go left.
3. Enter 1 — no left child. Emit 1. No right child; frame pops.
4. Back at 3: left flank done. Emit 3. Go right.
5. Enter 4 — leaf. Emit 4. Pop, pop.
6. Back at 5: emit 5. Go right.
7. Enter 8 — leaf. Emit 8.

Output: 1, 3, 4, 5, 8 — sorted, though the tree was fed a jumbled sequence. The stack’s deepest moment was three frames (5 → 3 → 1), which is the tree’s height plus one, and that observation is the space bound with its proof attached. Feed the same traversal a tree built from sorted input and the stack instead grows n deep before the first emission — the degenerate-shape lesson, again, from a different angle.

The invariant

When a node is emitted, its entire left subtree has already been emitted, and none of its right subtree has. By induction, everything smaller has been spoken and everything larger hasn’t — which is sortedness of the output, proved in a sentence. This is also the cleanest correct way to validate a BST: traverse in-order, check the emissions are strictly increasing. One previous-value variable, no bounds-passing, no cleverness — and it’s immune to the local parent-child trap that breaks naive validators.

The stack invariant is worth stating separately because iterative rewrites depend on it: the stack always holds exactly the ancestors whose own emission (and right subtree) is still pending. Every iterative in-order implementation is just this invariant maintained by hand.

Complexity, derived

Every node is entered once, emitted once, departed once: O(n) time, with a constant so small the traversal is usually memory-bound. The trace’s step count is checked to grow linearly, and the visualization’s counters show emissions ticking to exactly n. Space is the stack: O(h) — logarithmic on balanced trees, linear on chains, and that dependence on shape (not size) is what interviewers probe with “what’s the space complexity?” — the answer “O(h), which is O(n) worst case” collects both points.

Two space-related upgrades to have loaded: the iterative version (explicit stack, same O(h), no recursion-limit risk), and Morris traversal — O(1) space by temporarily threading each left subtree’s rightmost node to point back at the current node, using the tree itself as the stack, then unthreading on the second visit. Morris is rarely demanded, frequently name-dropped; being able to explain the threading trick in two sentences is the differentiator.

What people get wrong

Emitting before recursing left. One transposed line converts in-order into pre-order, output unsorted, and nothing crashes to tell you. The prediction prompt “which node is emitted first in this subtree?” exists precisely to make the leftmost-first reflex automatic.

k-th smallest via full traversal. Correct but wasteful: stop at the k-th emission — O(h + k), not O(n). With subtree-size augmentation it drops to O(h) per query, which is the follow-up’s follow-up.

Validating with node-local checks instead of the traversal. The increasing-sequence check is the clean validator; reaching for parent-child comparisons under pressure is the classic regression.

Stack discipline in the iterative form. The rhythm is: push the whole left spine; pop-and-emit; then take one step right and push that node’s left spine. Pushing the right child at the wrong moment reorders emissions subtly — test against the recursive version on an asymmetric tree.

Implementation notes across languages

Python: recursive is idiomatic until depth bites (default limit ~1000 — a chain-shaped tree from sorted input crosses it easily); the iterative form with a list-as-stack is the safe interview default. Generators shine here: yield from inorder(node.left) makes lazy traversal — stop at k-th smallest for free — though each yield from layer adds real per-element cost on deep trees. Java: Deque<Node> as the stack; note that TreeMap’s iterators are an in-order traversal productized, delivered incrementally. C++: std::set/std::map iteration is in-order by contract; writing it manually, prefer the explicit-stack loop. JavaScript: recursion depth limits vary by engine and are lower than people assume; the iterative version is the shippable one. Across all four: if you find yourself collecting the whole traversal into an array just to take element k, the lazy/early-exit version was the answer the question wanted.