Binary trees and traversals

What this chapter covers

A binary tree is the first branching structure in the book — nodes, each with up to two children — and the first thing you do with any tree is traverse it: visit every node in some order. There are exactly four orders worth knowing, and the surprise is how little separates them. Three are depth-first and differ by a single line — when you visit a node relative to its children — and the fourth is breadth-first and reuses the queue from earlier in the book. This chapter builds all four, shows why in-order is special for search trees, and sets up the next nine chapters, all of which are trees.

A bit of history

Trees are one of the oldest structures in computing, and their traversal orders were formalized early — Donald Knuth's Art of Computer Programming gave the in-order, pre-order, post-order names their standard meanings. Two of them have a deeper pedigree. In the 1920s the Polish logician Jan Łukasiewicz invented a parenthesis-free notation for logic, writing the operator before its operands — which is exactly pre-order traversal of an expression tree, and is still called Polish notation. Its reverse, operator after operands — post-order — became Reverse Polish Notation, the input method of HP calculators and the execution model of stack-based languages like Forth and PostScript. So two of this chapter's four traversals are how machines have evaluated arithmetic for a century: the tree shape and the visit order are the same idea seen from different angles.

The intuition

Picture a node with a left subtree and a right subtree. A depth-first traversal always does three things — handle the left subtree, handle the right subtree, and visit the node itself — the only question is the order. Visit the node between the subtrees and you get in-order; before them, pre-order; after them, post-order. That's the entire difference between the three: one line moves.

Which order you want is a question of when you need the node relative to its children. In-order, on a binary search tree, comes out sorted — because everything in the left subtree is smaller and everything in the right is larger, so visiting left-then-node- then-right yields ascending values. Pre-order gives you the root first, which is what you need to copy or serialize a tree (you can't rebuild a subtree before you know its root). Post-order gives you the children first, which is what you need to delete a tree (free the subtrees before the parent) or evaluate an expression tree (compute the operands before applying the operator). Level-order is the odd one out — it goes breadth-first, top to bottom, and needs a queue rather than recursion, because "nearest first" is a FIFO discipline, not a stack one.

Complexity: how it scales

Every traversal is $O(n)$ time — each of the n nodes is visited exactly once, and the work per node is constant. The space is $O(h)$, where h is the height of the tree: the depth-first traversals hold a recursion (or explicit) stack as deep as the current path, and level-order holds a queue as wide as the widest level. For a balanced tree $h = O(\log n)$, but for a degenerate one — a tree that's really a linked list — $h = O(n)$, which is where recursion can overflow the stack. The chart times recursive against iterative in-order on balanced trees:

Both are linear, as expected; the recursive version is about 1.2× slower here, the cost of the function-call overhead the explicit stack avoids.

What it's good at, what it isn't

Traversal is not optional — it's how you touch a tree's contents at all, so "what it's good at" is really "which order fits your task." In-order is the workhorse for search trees because it hands you sorted data for free. Pre- and post-order are the copy and delete/evaluate orders. Level-order is how you find the shallowest node matching some condition, or process a tree by generations. Knowing which is which turns a lot of tree problems into a one-line choice.

The thing to watch is recursion depth. The depth-first traversals are naturally recursive and beautifully short, but they use stack proportional to the tree's height, so a deep or unbalanced tree can blow the recursion limit — the same hazard from the recursion chapter. The iterative explicit-stack version dodges it, and the next several chapters (balanced trees) attack the root cause by keeping the height at O(log n).

The data, or the inputs

The correctness checks build search trees from random values and confirm in-order equals sorted. The face-off traverses balanced trees at growing sizes. The animation uses one fixed seven-node search tree so you can watch a single in-order traversal produce the sorted sequence, node by node.

Build it, one function at a time

In-order — visit the node between its subtrees, which yields sorted order for a BST:

def inorder(node, visit):
    """Left, node, right. For a binary SEARCH tree this yields the values in sorted
    order — the single most useful traversal, and the reason BSTs keep data ordered."""
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)

Pre-order — visit the node before its subtrees, for copying and serializing:

def preorder(node, visit):
    """Node, left, right. Visits a parent before its children — the order you use to
    copy or serialize a tree, because you need the root before its subtrees."""
    if node is None:
        return
    visit(node.value)
    preorder(node.left, visit)
    preorder(node.right, visit)

Post-order — visit the node after its subtrees, for deleting and evaluating:

def postorder(node, visit):
    """Left, right, node. Visits children before the parent — the order to delete a
    tree (free the subtrees first) or evaluate an expression tree (compute the
    operands before the operator)."""
    if node is None:
        return
    postorder(node.left, visit)
    postorder(node.right, visit)
    visit(node.value)

Level-order is the breadth-first one, and the only traversal that needs a queue instead of recursion:

def levelorder(root, visit):
    """Breadth-first: level by level, top to bottom, left to right — using a QUEUE.
    It's the one traversal that isn't naturally recursive; it's the tree version of
    breadth-first search, and it needs the FIFO queue from earlier in the book."""
    from collections import deque
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        visit(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

And here's the same in-order traversal without recursion, using an explicit stack — the recursion-to-stack transformation from earlier, applied to a tree:

def inorder_iter(root, visit):
    """In-order without recursion, using an EXPLICIT stack. This is the recursion-to-
    stack transformation from the recursion chapter applied to a tree: push lefts,
    visit, go right. It's what the recursive call stack was doing, made visible — and
    your escape hatch when a tree is too deep for Python's recursion limit."""
    stack, node = [], root
    while stack or node:
        while node:               # walk as far left as possible, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()        # backtrack to the deepest unvisited node
        visit(node.value)
        node = node.right         # then explore its right subtree

Watch it work

Here's an in-order traversal of a seven-node search tree. Orange is the node being visited right now; green nodes have been visited; dark nodes are still waiting. Step through it and watch the visit order: it dives down the left side to the smallest value, 1, then works rightward and upward — 3, 4, then the root 5, then the right subtree 7, 8, 9. The output builds up in the caption, and it comes out perfectly sorted, which is the whole reason in-order matters for search trees: the tree stores the data in a shape that makes sorted order a traversal away:

The complete code

Both versions in one place — flip between them. The from-scratch tab has all four traversals plus the iterative in-order. The library tab is the only honest counterpart: sorted, which is what in-order of a search tree must equal. There's no "traverse this tree" function in the standard library because a traversal is a technique, not a container — you write it, in whichever of these four shapes your task needs.

"""Binary tree traversals — the four ways to visit every node of a tree, and the
first thing you learn to do with one. A binary tree is nodes, each with up to two
children (left and right); a traversal is an order for touching all of them.

Three of the four are depth-first and fall out of recursion — they differ only in
WHEN you visit the node relative to its children. The fourth is breadth-first and
needs the queue from the linear-structures tier. Which order you want depends on the
job: in-order for sorted output, pre-order to copy, post-order to delete, level-order
to explore nearest-first.
"""


class Node:
    __slots__ = ("value", "left", "right")

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


# region: inorder
def inorder(node, visit):
    """Left, node, right. For a binary SEARCH tree this yields the values in sorted
    order — the single most useful traversal, and the reason BSTs keep data ordered."""
    if node is None:
        return
    inorder(node.left, visit)
    visit(node.value)
    inorder(node.right, visit)
# endregion


# region: preorder
def preorder(node, visit):
    """Node, left, right. Visits a parent before its children — the order you use to
    copy or serialize a tree, because you need the root before its subtrees."""
    if node is None:
        return
    visit(node.value)
    preorder(node.left, visit)
    preorder(node.right, visit)
# endregion


# region: postorder
def postorder(node, visit):
    """Left, right, node. Visits children before the parent — the order to delete a
    tree (free the subtrees first) or evaluate an expression tree (compute the
    operands before the operator)."""
    if node is None:
        return
    postorder(node.left, visit)
    postorder(node.right, visit)
    visit(node.value)
# endregion


# region: levelorder
def levelorder(root, visit):
    """Breadth-first: level by level, top to bottom, left to right — using a QUEUE.
    It's the one traversal that isn't naturally recursive; it's the tree version of
    breadth-first search, and it needs the FIFO queue from earlier in the book."""
    from collections import deque
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        visit(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
# endregion


# region: inorder_iter
def inorder_iter(root, visit):
    """In-order without recursion, using an EXPLICIT stack. This is the recursion-to-
    stack transformation from the recursion chapter applied to a tree: push lefts,
    visit, go right. It's what the recursive call stack was doing, made visible — and
    your escape hatch when a tree is too deep for Python's recursion limit."""
    stack, node = [], root
    while stack or node:
        while node:               # walk as far left as possible, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()        # backtrack to the deepest unvisited node
        visit(node.value)
        node = node.right         # then explore its right subtree
# endregion

"""There's no "traverse a tree" function in the standard library — a traversal is a
technique, not a container, so the honest counterparts are references:

  - For a binary SEARCH tree, in-order traversal must equal `sorted(values)` — that's
    the property that makes in-order special, and the reference we check against.
  - The recursive and iterative (explicit-stack) traversals must agree with each
    other — that's the recursion-to-stack transformation, and its own reference.

So the face-off is recursive vs iterative in-order (do they match, and what does the
recursion cost?), with `sorted` confirming that in-order of a BST is sorted order.
"""


# region: sorted_reference
def inorder_reference(values):
    """The reference for in-order of a binary SEARCH tree: it is exactly the sorted
    values. If your in-order traversal doesn't equal this, the tree isn't a valid BST
    (or the traversal is wrong)."""
    return sorted(values)
# endregion

Scratch vs library

There isn't a library to race here — the standard library doesn't traverse trees for you — so the meaningful comparison is recursive versus iterative in-order, and the verification that in-order of a search tree equals sorted. Recursive traversal ran about 1.2× slower than the explicit-stack version on 160000 nodes, the function-call overhead again, but the recursive code is so much clearer that you'd reach for it every time the tree is known to be shallow — which, once we have balanced trees, is always. The deeper result is the one the animation showed: in-order traversal turns a binary search tree into sorted output in O(n), for free, which is the property that makes the next chapter's structure worth building.

Where you'll actually meet it

You traverse trees constantly, usually through something built on top. Every compiler walks the syntax tree of your code — pre-order to build symbol tables, post-order to generate or evaluate. Serializing JSON or XML is a pre-order traversal; a recursive directory listing is a tree traversal of the filesystem; rendering the DOM walks the document tree. os.walk, json.dump, and every "visit all the nodes" operation in a UI framework is one of these four orders. And in-order specifically is how ordered maps and sets (built on search trees) iterate their keys in sorted order — the subject of the whole rest of this tier.

Takeaways

A binary tree is nodes with up to two children, and the four traversals are the four orders to visit them: in-order (sorted, for a BST), pre-order (copy), post-order (delete/evaluate), and level-order (breadth-first, with a queue). The three depth-first orders are one algorithm with the visit moved before, between, or after the recursion; all four are $O(n)$ time and $O(h)$ space. The recursion is clean but depth-bounded, which is one more reason to want the balanced trees ahead.

The star result is in-order on a search tree yielding sorted order — which is a promise about a structure we haven't built yet. The next chapter builds it: the binary search tree, where the ordering rule (smaller left, larger right) makes search, insert, and delete all follow a single downward path, and in-order traversal reads the whole thing out in order.