DSA Traversals

In-order Traversal

You need every SKU in a live BST listed in catalog order without copying keys into an array and sorting. At n = 10⁶, an extra Θ(n log n) sort after a walk is wasted work if the tree already encodes order.

(Left → Root → Right) is the walk that turns the search-tree invariant into . On a non-BST binary tree, the same walk is still valid structure, just not sorted.

Algorithm journey

Finish left first

Suspend the node until its left subtree is fully emitted.

Emit at the boundary

Visit between left and right subproblems.

Then right

Only after the visit enter the right subtree.

Ancestors awaiting their visit after left completion.

What actually happens

Naive idea: collect all keys, then sort. Correct, and Θ(n log n) after Θ(n) collection. On a BST you already paid to maintain order.

Better idea: recurse left, emit, recurse right. The structural order matches key order exactly when the BST invariant holds.

The improved design still fails if the tree is not a BST (output is unsorted), if you validate a BST with pre-order instead of adjacent in-order keys, or if aborts mid-walk and leaves threads behind.

Invariant / guarantee

For every node x, every node in x's left subtree appears before x in the output, and x appears before every node in x's right subtree. On a valid BST with a strict unique-key policy, that sequence is strictly increasing.

How to choose in-order

1. Need sorted BST keys or kth smallest? In-order (with early stop for kth).

2. Need parent before children? Pre-order. Need children before parent? Post-order.

3. Need O(1) aux space? Consider Morris only if temporary mutation is acceptable.

Quantitative check

Full walk: Θ(n) time. Finding the kth smallest can stop after k emits: O(h + k). At n = 10⁶ balanced, h ≈ 20; a skewed tree makes even “k = 1” cost Θ(n) descent.

The subtree contract

1 · left

Finish the left subtree first

The current node remains suspended while the entire left subtree is emitted.

2 · root

Emit at the boundary

The visit marks the boundary between this node's left and right subtree output.

3 · right

Finish the remaining structure

Only after the node is emitted does traversal enter its right subtree.

Build and traverse a tree

Build a tree, start in-order, and watch each node appear only after its left subtree has finished.

Build a tree and click Play!

Result:

Empty Tree

The left-ancestor frontier

The explicit stack is not an arbitrary bag of nodes: it is the path of ancestors waiting for their left subtree to finish. Compare it with the suspended recursive frames.

Frames, continuations, and output

Follow the same in-order contract implemented by the language call stack or by an explicit stack.

Step 1 of 43

Ready to call walk(A)

The output and the language call stack both start empty.

Stack (top first)

empty

Output prefix

Nothing visited yet

Invariant: For each completed node, its left subtree has been emitted, then the node, while its right subtree follows.

Timeline

Recursive implementation

The null case is the empty-subtree result. The append occurs between two complete recursive calls.

Python

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def inorder(root):
    result = []

    def walk(node):
        if node is None:
            return
        walk(node.left)
        result.append(node.value)
        walk(node.right)

    walk(root)
    return result


root = Node(4, Node(2, Node(1), Node(3)), Node(6))
print(inorder(root))  # [1, 2, 3, 4, 6]

Java

java

import java.util.ArrayList;
import java.util.List;

public class InorderRecursive {
    static class Node {
        int value;
        Node left, right;

        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static List<Integer> inorder(Node root) {
        List<Integer> result = new ArrayList<>();
        walk(root, result);
        return result;
    }

    static void walk(Node node, List<Integer> result) {
        if (node == null) return;
        walk(node.left, result);
        result.add(node.value);
        walk(node.right, result);
    }

    public static void main(String[] args) {
        Node root = new Node(4,
            new Node(2, new Node(1), new Node(3)),
            new Node(6));
        System.out.println(inorder(root)); // [1, 2, 3, 4, 6]
    }
}

Iterative implementation

Two conditions drive the loop: a non-null cursor means there is more left descent; a non-empty stack means an ancestor still needs to be visited.

Python

python

def inorder_iterative(root):
    result = []
    stack = []
    current = root

    while current is not None or stack:
        # Establish the invariant: stack is the left-ancestor path.
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.value)
        current = current.right

    return result

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

final class InorderIterative {
    static final class Node {
        final int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }

    static List<Integer> traverse(Node root) {
        List<Integer> result = new ArrayList<>();
        Deque<Node> stack = new ArrayDeque<>();
        Node current = root;

        while (current != null || !stack.isEmpty()) {
            // Stack is the path of ancestors awaiting their visit.
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            result.add(current.value);
            current = current.right;
        }
        return result;
    }
}

Morris traversal: O(1) auxiliary space

Morris traversal temporarily points each node's in-order predecessor back to that node. The first encounter creates the thread; the second encounter removes it and emits the node. Every temporary pointer must be restored.

Python

python

def inorder_morris(root):
    result = []
    current = root

    while current is not None:
        if current.left is None:
            result.append(current.value)
            current = current.right
            continue

        predecessor = current.left
        while (predecessor.right is not None
               and predecessor.right is not current):
            predecessor = predecessor.right

        if predecessor.right is None:
            predecessor.right = current  # create return thread
            current = current.left
        else:
            predecessor.right = None     # restore original tree
            result.append(current.value)
            current = current.right

    return result

Java

java

import java.util.ArrayList;
import java.util.List;

final class InorderMorris {
    static final class Node {
        final int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }

    static List<Integer> traverse(Node root) {
        List<Integer> result = new ArrayList<>();
        Node current = root;

        while (current != null) {
            if (current.left == null) {
                result.add(current.value);
                current = current.right;
                continue;
            }

            Node predecessor = current.left;
            while (predecessor.right != null
                    && predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                predecessor.right = current; // create return thread
                current = current.left;
            } else {
                predecessor.right = null;    // restore original tree
                result.add(current.value);
                current = current.right;
            }
        }
        return result;
    }
}

Use with care: Morris temporarily mutates the tree. Avoid it for immutable nodes, concurrent readers, or callbacks that may abort traversal before threads are restored. O(1) auxiliary space is not automatically worth the operational risk.

Why a BST comes out sorted

For every BST node, every allowed key in its left subtree precedes the node's key under the tree's comparator, and every allowed key in its right subtree follows it. In-order recursively emits those three regions in exactly that sequence. If duplicate nodes are allowed, the result is non-decreasing; it is strictly increasing only when duplicate keys are forbidden or coalesced into one node.

The converse warning matters: in-order traverses any binary tree, but its output is sorted only when the BST ordering invariant actually holds.

Complexity comparison

Comparison of recursive, explicit-stack, and Morris in-order traversal
Method	Time	Auxiliary space	Trade-off
Recursive	Θ(n)	Θ(h)	Clearest contract; runtime stack can overflow on a deep chain.
Explicit stack	Θ(n)	Θ(h)	Depth-safe and resumable; manages state directly.
Morris	Θ(n)	Θ(1)	No stack, but temporarily rewires pointers and has larger constants.

Here h is tree height: Θ(log n) for a height-balanced tree and Θ(n) for a skewed tree. A returned list itself costs Θ(n) and is not counted as auxiliary workspace.

Applications and edge cases

Natural applications

Enumerating BST keys in comparator order.
Finding the kth smallest key with early termination.
Validating a BST by checking adjacent emitted keys.
Rendering a binary expression with operators between operands.

Questions to settle

Empty trees produce an empty sequence.
Duplicate-key policy must agree with the BST comparator.
Cycles or shared subtrees violate ordinary tree assumptions.
For lazy iteration, preserve the stack and cursor between yields.

Exercises

Prove that in-order on a valid BST with distinct keys is strictly increasing. Where does the argument use the search-tree invariant?
Give a binary tree that is not a BST whose in-order sequence looks “almost sorted.” What single swap of keys would an adjacent-check validator catch?
Compare recursive, explicit-stack, and Morris for a read-only tree shared across threads. Which options are safe, and why?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): inorder tree walk and BST sorting property.
Morris, Joseph M. (1979): Traversing binary trees simply and cheaply (threaded O(1)-space walk).
Sedgewick & Wayne: inorder as the natural iterator for BST symbol tables.