Preorder, Inorder, Postorder Traversals

The Question Traversal Answers

A tree is a fundamentally two-dimensional object — children branch sideways from each parent. But almost every operation we want to perform on it (print it, save it to disk, compute a checksum, hand it to another function) demands a one-dimensional answer: a list, a string, a stream of bytes. The bridge between those two worlds is a traversal: a deterministic rule for visiting every node exactly once and turning the tree into a sequence.

For binary trees, three traversal rules dominate every textbook, every parser, every database engine, every git internals manual: preorder, inorder, and postorder. They are not arbitrary. They correspond to the three positions where you can place “visit the root” among “walk the left subtree” and “walk the right subtree” — and each position turns out to encode a different real-world meaning.

The single insight of this section: a tree has many useful linearizations. Preorder, inorder, and postorder are the three you can build by recursive descent, and which one you pick is a statement about when the parent's work happens relative to its children.

Three Orders, One Recursion

Every binary-tree traversal we will study has the same three-line skeleton:

1def walk(node):
2    if node is None: return
3    # ... three things to do, in some order:
4    #   visit(node)
5    #   walk(node.left)
6    #   walk(node.right)

The three orderings of those three statements with visit in different positions give us the three names:

The other three permutations (right-first variants like visit, right, left) exist and are called reverse preorder/inorder/postorder. They produce the mirror of the originals on a flipped tree, and we rarely need them as primitives. The three above are the canonical set.

The Recurrence and Its Mathematics

Let $T$ be a binary tree with root $r$, left subtree $L$, and right subtree $R$. Let $\text{Pre}(T)$, $\text{In}(T)$, and $\text{Post}(T)$ denote the sequences produced by the three traversals. Each obeys a clean recurrence:

• $\text{Pre}(T) = [r] \cdot \text{Pre}(L) \cdot \text{Pre}(R)$ — root, then preorder of left, then preorder of right.
• $\text{In}(T) = \text{In}(L) \cdot [r] \cdot \text{In}(R)$ — inorder of left, root, inorder of right.
• $\text{Post}(T) = \text{Post}(L) \cdot \text{Post}(R) \cdot [r]$ — postorder of left, postorder of right, root.
• Base case for all three: $\text{Pre}(\emptyset) = \text{In}(\emptyset) = \text{Post}(\emptyset) = [\,]$.

From these recurrences we can already prove three properties without writing any code. Let $n(T)$ be the number of nodes and $h(T)$ the height (longest root-to-leaf path).

• Length. $|\text{Pre}(T)| = |\text{In}(T)| = |\text{Post}(T)| = n(T)$. By induction on the recurrence: each contributes $1 + n(L) + n(R) = n(T)$. Every node appears exactly once, no matter the order.
• Time. The recurrence $T(n) = T(n_L) + T(n_R) + O(1)$ with $n_L + n_R = n - 1$ solves to $T(n) = \Theta(n)$. Linear in the size of the tree, regardless of shape.
• Space. Recursion depth equals the height: $S(n) = O(h(T))$. For a balanced tree that is $O(\log n)$; for a degenerate path-like tree it is $O(n)$. This is why pathological trees are dangerous on platforms with fixed-size stacks.

Worked Example: One Tree, Three Walks

Consider the seven-node tree:

11
2           / \
3          2   3
4         / \ / \
5        4  5 6  7

Apply each recurrence by hand. The bracketed comments show which substitution we just made.

Three properties to notice in the sequences themselves, before we touch any code:

• Preorder starts with the root (the first element is always $r$). Everything after it is the preorder of one of the children.
• Postorder ends with the root (the last element is always $r$). Read postorder backwards and you are reading reverse-preorder of the mirror tree.
• Inorder splits at the root. If you know the root, everything to its left in the inorder array is the inorder of the left subtree, and everything to the right is the inorder of the right subtree. This is the fact that lets us reconstruct a tree from preorder + inorder uniquely — a classic interview problem.

Interactive: Step-by-Step Traversal

Theory is cheap; intuition is expensive. The visualizer below runs each traversal one frame at a time on the same seven-node tree, animating the recursion stack on the right exactly as it would appear in a debugger. Switch the order, step through, replay — the goal is to see why the same shape of recursion produces three different sequences.

Implementation in C (Recursive)

C is the right starting language because it makes the cost model painfully explicit: every node is an explicit pointer, every recursive call is an explicit stack frame, and the only way to release memory is to walk the tree once more.

1// tree.h ------------------------------------------------------------
2typedef struct Node {
3    int value;
4    struct Node *left;
5    struct Node *right;
6} Node;
7
8// Allocate a leaf with a given value.
9Node *make_node(int v) {
10    Node *n = (Node *) malloc(sizeof(Node));
11    if (n == NULL) {
12        fprintf(stderr, "out of memory\n");
13        exit(1);
14    }
15    n->value = v;
16    n->left = NULL;
17    n->right = NULL;
18    return n;
19}
20
21// traverse.c --------------------------------------------------------
22void preorder(const Node *root) {
23    if (root == NULL) return;          // base case: empty subtree
24    printf("%d ", root->value);        // VISIT (root first)
25    preorder(root->left);              // then left subtree
26    preorder(root->right);             // then right subtree
27}
28
29void inorder(const Node *root) {
30    if (root == NULL) return;
31    inorder(root->left);               // left
32    printf("%d ", root->value);        // VISIT (root in the middle)
33    inorder(root->right);              // right
34}
35
36void postorder(const Node *root) {
37    if (root == NULL) return;
38    postorder(root->left);             // left
39    postorder(root->right);            // right
40    printf("%d ", root->value);        // VISIT (root last)
41}
42
43// Driver
44int main(void) {
45    // Build:        1
46    //              / \
47    //             2   3
48    //            / \ / \
49    //           4  5 6  7
50    Node *r = make_node(1);
51    r->left  = make_node(2);
52    r->right = make_node(3);
53    r->left->left  = make_node(4);
54    r->left->right = make_node(5);
55    r->right->left  = make_node(6);
56    r->right->right = make_node(7);
57
58    preorder(r);   printf("\n");   // 1 2 4 5 3 6 7
59    inorder(r);    printf("\n");   // 4 2 5 1 6 3 7
60    postorder(r);  printf("\n");   // 4 5 2 6 7 3 1
61
62    free_tree(r);                  // postorder freeing — see below
63    return 0;
64}

Three observations that are easy to miss but matter for production code:

• The base case root == NULL is not optional. Without it, the recursion would dereference a null pointer at the first leaf and crash. The base case is what makes the recursion close on itself.
• const Node *root documents read-only intent. Traversals never mutate structure; the const qualifier lets the compiler enforce that promise and lets callers pass in a const Node * without a cast.
• Freeing the tree is itself a postorder traversal. The reason: you must free the children before the parent, otherwise parent->left would be a dangling pointer the moment you dereferenced it. We will revisit this in the applications section — it is the prototype example of why postorder exists.

The Same Algorithms in Python

The Python translation is line-for-line identical in structure. The differences are ergonomic — automatic memory management, list as the visit accumulator, no explicit pointers — but the algorithm is exactly the same. Read the explanations carefully: the line-position trick in the recursive body is the entire idea you take from this section.

preorder(root, out=[])  # caller passes the same list to every recursive call

out.append(root.value)  # root → output BEFORE descending

freeing memory:  free(left); free(right); free(self)  ← postorder

1# A textbook binary tree node.
2class Node:
3    __slots__ = ("value", "left", "right")
4    def __init__(self, value, left=None, right=None):
5        self.value = value
6        self.left  = left
7        self.right = right
8
9def preorder(root, out):
10    if root is None:                # base case
11        return
12    out.append(root.value)          # VISIT root
13    preorder(root.left,  out)       # then left
14    preorder(root.right, out)       # then right
15
16def inorder(root, out):
17    if root is None:
18        return
19    inorder(root.left,  out)        # left
20    out.append(root.value)          # VISIT root in the middle
21    inorder(root.right, out)        # right
22
23def postorder(root, out):
24    if root is None:
25        return
26    postorder(root.left,  out)      # left
27    postorder(root.right, out)      # right
28    out.append(root.value)          # VISIT root last
29
30# Build the same 7-node tree
31r = Node(1,
32        Node(2, Node(4), Node(5)),
33        Node(3, Node(6), Node(7)))
34
35pre, ino, post = [], [], []
36preorder(r, pre);   print(pre)    # [1, 2, 4, 5, 3, 6, 7]
37inorder(r, ino);    print(ino)    # [4, 2, 5, 1, 6, 3, 7]
38postorder(r, post); print(post)   # [4, 5, 2, 6, 7, 3, 1]

Iterative Traversal with an Explicit Stack

The recursive versions are elegant but they trust the runtime stack. When the tree might be very deep (parsed user input, file-system trees, malicious data, embedded systems with tiny stacks) we want to manage the stack ourselves. The good news: every recursion can be unrolled into an explicit stack, and tree traversal is the cleanest example of that transformation in the whole curriculum.

modified preorder: 1 3 7 6 2 5 4   →  reversed:  4 5 2 6 7 3 1  ✓

1# Iterative inorder using an explicit stack.
2# This is exactly what the recursive version is doing under the hood —
3# we are just managing the stack ourselves instead of letting the runtime do it.
4
5def inorder_iter(root):
6    out, stack = [], []
7    cur = root
8    while cur is not None or stack:
9        # 1. walk all the way left, pushing every node we pass.
10        while cur is not None:
11            stack.append(cur)
12            cur = cur.left
13        # 2. no more left to descend → pop and visit.
14        cur = stack.pop()
15        out.append(cur.value)
16        # 3. now turn right and repeat.
17        cur = cur.right
18    return out
19
20# Iterative preorder: the cleanest of the three.
21def preorder_iter(root):
22    if root is None:
23        return []
24    out, stack = [], [root]
25    while stack:
26        node = stack.pop()
27        out.append(node.value)            # visit immediately
28        # Push RIGHT first so LEFT pops next — preorder = root, left, right.
29        if node.right is not None:
30            stack.append(node.right)
31        if node.left  is not None:
32            stack.append(node.left)
33    return out
34
35# Iterative postorder using two stacks (the easy way).
36def postorder_iter(root):
37    if root is None:
38        return []
39    s1, s2 = [root], []
40    while s1:
41        node = s1.pop()
42        s2.append(node)                   # collect in reverse-postorder
43        if node.left  is not None: s1.append(node.left)
44        if node.right is not None: s1.append(node.right)
45    return [n.value for n in reversed(s2)]

The deep takeaway: a recursive traversal and a stack-based iterative traversal are the same algorithm. The recursion uses the call stack the language gave it for free; the iterative version uses a list it manages by hand. They both push when descending, pop when returning, and visit nodes in the same order. The cost model is identical: $\Theta(n)$ time and $O(h)$ auxiliary space.

Time, Space, and Correctness

We summarized the complexity already; here is the more careful breakdown side by side.

Why the analysis is so clean. Each node is the focus of exactly one recursive call (or one push/pop on the iterative side). The work at the focus is $O(1)$ — a comparison, an append, perhaps a print. Sum over all $n$ nodes and you get $\Theta(n)$. There is no slack and there are no hidden quadratic costs as long as you avoid the return new_list = recurse(left) + [root] + recurse(right) pattern, which copies lists and turns linear into quadratic.

Why it is correct. Structural induction: assume $\text{Pre}, \text{In}, \text{Post}$ are correct on the two subtrees $L$ and $R$; the recurrence then constructs the correct sequence for $T$ by definition. The base case (empty tree → empty list) is trivially correct. Induction does the rest.

Where Each Order Lives in Real Systems

The three traversals are not academic curiosities. Each one solves a class of problems where the timing of “visit the parent” relative to “visit the children” carries meaning.

Preorder — “parent first”

• File-system listings like find, ls -R, and tree-style dumps print the directory before its contents. The output reads top-down, which is what users expect.
• Tree serialization / cloning. When you serialize a tree to JSON or to disk, the natural order is preorder (root, then children) so the reader can construct the parent first and attach children as they arrive. Git's tree objects, S-expressions, and most AST dump formats all use preorder.
• Prefix expressions in Lisp: (+ 1 (* 2 3)) is the preorder of the expression tree.
• DOM rendering in browsers: when the layout engine decides where each element goes, it measures parents before children — a preorder pass.
• Tree pretty-printers in compilers (clang -ast-dump, rustc HIR dumps) emit nodes in preorder so an indented stream visually matches the tree shape.

Inorder — “parent in the middle”

• BST iteration. The single most important application: inorder of a binary search tree visits keys in sorted order. Database indices built on B-trees and B+ trees use the same idea (generalized to many-way nodes).
• Range queries. Once you can iterate inorder, you can stop at any predicate — give me all keys in $[a, b]$ by descending to $a$, then inorder-iterating until you exceed $b$.
• Infix-notation expression trees. If a node represents a binary operator and its children are the operands, inorder yields the human-readable infix form (after adding parentheses for precedence).
• Music sequencers and beat-tree models for rhythm: inorder traversal of a metric tree gives the order in which beats are played.
• Threaded binary trees exploit inorder so heavily that they thread otherwise-null child pointers to point at the inorder predecessor/successor — turning iteration into $O(1)$ per step with no stack.

Postorder — “children before parent”

• Memory deallocation (free_tree in C, RAII destructors in C++). You must free the children before the parent — otherwise the parent's child pointers become stale before you have visited them.
• Postfix (Reverse Polish) notation. 1 2 3 * + is the postorder of the expression tree for $1 + 2 \times 3$. HP calculators, Forth, PostScript, and the JVM bytecode evaluator all consume postfix because it requires only a stack — no operator-precedence parsing at evaluation time.
• Dependency resolution. Build systems (make, Bazel, npm) topologically sort tasks via postorder of the dependency DAG: a task is emitted only after every prerequisite is emitted. The same logic schedules cells in spreadsheets and resolves layout in CSS.
• Subtree aggregations — sum, max, height, count, hash, AABB union, signed-distance merging in spatial data structures. The parent's aggregate requires the children's aggregates, so the parent runs last.
• Code generation in compilers. To emit code for an expression node, you first emit code that computes its children into registers — postorder on the AST.
• Lock release in nested scopes and transaction unwinding: locks are released in the reverse order they were acquired, which is exactly postorder of the scope tree.

Pitfalls and Edge Cases

The empty tree

Every implementation must handle root is None gracefully. The recurrence dictates an empty output. Skipping the base case crashes; turning it into raise is overzealous — the empty traversal is well-defined and frequently useful (e.g. when a subtree is genuinely missing in a serialized format).

Returning new lists at every recursive call

The seductive but quadratic mistake:

1def preorder_bad(root):
2    if root is None: return []
3    return [root.value] + preorder_bad(root.left) + preorder_bad(root.right)

Each + copies the entire accumulating list. On a balanced tree the work is $T(n) = 2T(n/2) + O(n)$, giving $O(n \log n)$; on a path-shaped tree it is $O(n^2)$. Always pass an accumulator (the “out” list pattern) or use yield for a generator. The complexity bug is invisible on toy inputs and lethal at scale.

Push order on iterative stacks

Pushing children onto the stack reverses the order in which they will be processed. For preorder you push right then left so left pops first. Get this backwards and you produce a mirror traversal — silently wrong, no exception.

Confusing inorder with sorted-order on non-BSTs

Inorder yields sorted output only when the tree satisfies the BST property. On a generic binary tree it just produces some permutation of the values. Beginners memorize “inorder is sorted” and apply it everywhere; the correct rule is “inorder of a BST is sorted”.

Stack overflow on adversarial input

A linked-list-shaped tree built from sorted inserts into an unbalanced BST can have height equal to$n$. On Python, that triggers RecursionError at about 1000 levels by default. Defenses: sys.setrecursionlimit (cheap, papers over the symptom), switch to the iterative version (correct), or rebalance the tree (correct and faster long-term).

Modifying the tree while traversing it

If visit deletes nodes, splices in subtrees, or rotates ancestors, the recursion sees an inconsistent state. The classic safe pattern is “collect first, mutate later”: do a read-only traversal that produces a list of work items, then process the list in a second pass.

Quick Checks

The three orders feel like minor permutations, but they are the foundation on which BSTs, ASTs, build systems, garbage collectors, and database indices stand. The next section turns the camera 90° and looks at level-order traversal — visiting a tree breadth-first instead of depth-first — which uses a queue instead of a stack and unlocks an entirely different family of applications.