How In-Order Traversal Works

In-order traversal visits the left subtree, then the node, then the right subtree. On a binary search tree that emits every value in ascending order, which is the property most BST work rests on.

Output so far

Nothing yet.

Not reached
On the stack
Current
Visited

1/19

In-order walk over 7 values, 3 levels deep.

Counters

Visited: 0/7
On the stack: 0
Tree height: 3
Nodes: 7

Settings

How many values7

More options

How it was built

In-order

1stack = []; node = root
2while node or stack:
3 while node:
4 stack.push(node)
5 node = node.left
6 node = stack.pop()
7 visit(node)
8 node = node.right

What each walk is for

Walk	What you get	Time	Extra space
In-order	Values in sorted order	O(n)	O(h)
Pre-order	Root before children, for copying a tree	O(n)	O(h)
Post-order	Children before root, for freeing or evaluating	O(n)	O(h)
Level-order	Shallowest nodes first, level by level	O(n)	O(w)
Search	One value, by comparing at each node	O(h)	O(1)

Scroll the table sideways for the rest of the columns.

n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n, which is what balancing prevents.

Complexity

Best	Average	Worst	Extra memory
O(n)	O(n)	O(n)	O(h)

h is the tree's height: O(log n) balanced, O(n) for a tree built from sorted inserts. The space is the call stack, or the explicit stack that replaces it.

How in-order traversal works

In-order traversal recurses into the left child, visits the current node, then recurses into the right child. In a binary search tree everything left of a node is smaller and everything right is larger, so that ordering emits the values sorted without a single comparison being made during the walk. Sorting a BST is free. The work was already done at insertion time.

If the node is empty, return.
Traverse the left subtree in full.
Visit the node. This is where the value is emitted.
Traverse the right subtree in full.

Implementation

def in_order(node, visit):
    if node is None:
        return
    in_order(node.left, visit)
    visit(node.value)
    in_order(node.right, visit)


def in_order_iterative(root):
    """The same walk without recursion, for trees deep enough to overflow."""
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.value)
        node = node.right
    return out

When to use it

Use it whenever a BST needs to be read in order: range queries, sorted exports, or finding the k-th smallest value.
Use it to check that a tree really is a valid BST. The in-order sequence has to be strictly increasing, and that is a cleaner test than comparing each node with its children.
Use an explicit stack rather than recursion for deep trees, where a degenerate shape would otherwise overflow the call stack.

Check yourself

Why does in-order traversal of a BST come out sorted?

Because the BST invariant says everything in the left subtree is smaller than the node and everything in the right is larger. Visiting left, then node, then right emits those three groups in exactly that order, recursively - so the whole sequence is ascending.

How would you check that a tree really is a valid BST?

Walk it in order and confirm the sequence is strictly increasing. Comparing each node only with its immediate children is not enough: a node can be larger than its left child and still violate the invariant against a grandparent.

The recursive version is four lines. Why would anyone write the iterative one?