In-order traversal

In-order traversal is a depth-first walk of a Binary tree that processes the current node between its children: traverse left subtree, process current node, traverse right subtree. The acronym LNR (Left-Node-Right) captures it.

inorder(root) → inorder(left), then root, then inorder(right)

The reason it matters: in-order traversal of a BST visits nodes in sorted order. That’s the most common reason to use it — cleanest way to get a sorted sequence out of a BST.

Recursive implementation

void inorderPrint(BinaryTreeNode *cur) {
    if (cur == NULL) return;
    inorderPrint(cur->left);
    printf("%d ", cur->data);              // node visited between its subtrees
    inorderPrint(cur->right);
}

The middle line is what distinguishes in-order from pre-order (line first) and post-order (line last).

Why in-order produces sorted output on a BST

A BST satisfies the invariant: for every node, all left-subtree keys are less, all right-subtree keys are greater. By induction, in-order traversal:

1. Recursively prints the left subtree (all keys $<$ current) in sorted order.
2. Prints the current key.
3. Recursively prints the right subtree (all keys $>$ current) in sorted order.

The output is the concatenation: smaller keys, then current, then larger keys, so sorted overall. One walk of the tree gives every key in order in $O(n)$, no extra sorting.

This is why BSTs are good for ordered traversal, range queries, and finding successors/predecessors.

Worked example

In-order does not by itself sort — it only produces sorted output when the tree is a BST. Two cases make this concrete.

Non-BST. Take a tree with root 7, left child 12 (children −2 and 22), right child 15 (left child −19). This breaks the BST invariant — 12 and 22 exceed 7 yet sit in 7’s left subtree. In-order (LNR) gives -2 12 22 7 -19 15: the correct LNR order, but with no sorted guarantee.

BST. Now the standard sorted binary tree, which is a BST (every left key smaller, every right key larger): root F; F’s children B (left) and G (right); B’s children A and D; D’s children C and E; G’s right child I, whose left child is H. In-order visits the deepest-left node first and climbs left-to-right across the tree:

Image: Sorted binary tree showing in-order traversal, public domain

In-order output: A B C D E F G H I, sorted ascending. Every key in order from a single $O(n)$ pass.

Iterative implementation with an explicit stack

void inorderIterative(BinaryTreeNode *root) {
    Stack s = stack_create();
    BinaryTreeNode *cur = root;
    while (cur != NULL || !stack_empty(&s)) {
        while (cur != NULL) {
            stack_push(&s, cur);
            cur = cur->left;
        }
        cur = stack_pop(&s);
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

Walk left as far as possible, pushing onto the stack. Pop, process, then move right and repeat. The stack remembers the path of unvisited ancestors.

Morris traversal — $O(1)$ space

The classic recursive and iterative versions both use $O(h)$ space. Morris traversal does in-order in $O(1)$ space by temporarily threading the tree: each leftmost-of-right-subtree node points back to its in-order predecessor. After the predecessor is visited, the thread is removed and the algorithm moves right. Constant space, $O(n)$ time, but it mutates the tree mid-traversal, so watch out in concurrent contexts.

Use cases

• BST sorted output. The single biggest reason to use in-order.
• Range queries on BSTs. In-order between two keys gives all keys in the range.
• Finding in-order successor. During BST deletion of a node with two children, the in-order successor (smallest key in the right subtree) replaces the deleted node.
• Infix expression output. In-order of an expression tree gives infix notation — though without parentheses you can lose precedence information, so it’s mostly for visualisation.
• Validating a BST. A binary tree is a BST iff its in-order traversal is sorted. Use this as a debug check.

Complexity

Time $O(n)$, recursive space $O(h)$, Morris space $O(1)$.

Comparison

Order	Sequence	BST output
Pre-order	Root, Left, Right	Not sorted
In-order	Left, Root, Right	Sorted ascending
Post-order	Left, Right, Root	Not sorted
Level-order	By depth	Not sorted

For the hub note, see Binary tree traversal.