Trees and Traversal

A tree is a set of nodes in which every node except one has exactly one parent. That is the shape of anything that nests: folders inside folders, tags inside tags, expressions inside expressions. The file system, the document a browser builds from a page of HTML, the JSON a service parses on every request and the syntax tree of every program you run are all trees.

Walking a tree visits every node once, so a walk is O(n). What the walk can compute depends on the order of the visit, parent before children or children before parent, and the wrong order does not produce a slow answer. It produces a wrong one: a directory that refuses to be deleted, or a folder size totalled before its contents were counted.

Root, Leaf, Depth and Height

The root is the one node with no parent. A leaf is a node with no children. A node's depth is its distance from the root, counted in edges, so the root sits at depth 0 and its children at depth 1. The tree's height is the greatest depth of any node. A tree of height 3 has four levels, and reaching its deepest leaf from the root takes three steps down.

Two numbers bound the cost of reaching anything in a tree: its fan-out, the number of children per node, and its height. They are the thread through this whole chapter. A million nodes arranged as a balanced binary tree, two children each, stand 20 levels deep. Give every node a hundred children and the same million sit at most 3 steps below the root, because a hundred times a hundred times a hundred is a million. Let the tree degenerate into a line, one child per node, and it is a million levels deep. Same nodes, same data, and the cost of reaching the bottom differs by a factor of fifty thousand.

Pre-Order and Post-Order

A pre-order walk handles a node before its children. A post-order walk handles a node after all of them. The choice follows from which side needs the other, and taste has nothing to do with it.

Copying a directory tree is pre-order, because a folder must exist before anything can be written into it. Printing a folder listing is pre-order too, since each folder's name comes before its contents. Deleting a directory tree is post-order, because a folder can be removed only once it is empty. Totalling a folder's size is post-order, because the total needs every child's size first. Run a delete in pre-order and the first step fails on a folder that still has files in it.

In-Order and Level-Order

In-order visits the left subtree, then the node, then the right subtree. It exists only for binary trees, where each node has a left and a right child, and on a binary search tree it visits the keys in sorted order, which the next topic depends on.

Level-order visits the tree one depth at a time: the root, then all its children, then all their children. It needs a queue, the structure from Chapter 5: take a node from the front, handle it, and put its children at the back. Children queued behind their whole level come out only after that level is finished. This is breadth-first search, which Chapter 8 generalizes to graphs, and it is how a file browser shows the first two levels of a folder before it has read the rest.

Recursion and an Explicit Stack

The natural way to write a walk is a function that calls itself on each child. Each call waits on the call stack while its children are handled, so the recursion depth equals the height of the tree. Chapter 3 showed that the call stack has a limit; in CPython the default recursion limit is 1,000 frames.

def depth(node):                          # recursion: one frame per level
    return 1 + max((depth(c) for c in node), default=0)

def depth_iterative(node):                # its own stack: a list in memory
    best, stack = 0, [(node, 1)]
    while stack:
        n, d = stack.pop()
        best = max(best, d)
        stack.extend((c, d + 1) for c in n)
    return best

Both functions above answer the same question for a document of nested lists. The first calls itself once per level, so its depth is the document's depth. The second keeps the nodes still to visit in an ordinary list and loops until the list is empty, so a deeper tree costs it more memory and nothing else. Measured on Python 3.15, the standard library's JSON parser accepted a document nested 5,000 levels deep without complaint, and the recursive walk over the result raised RecursionError. The iterative walk returned 5,000.

The parser itself has a ceiling too, only further away: it decoded 100,000 levels of nesting and raised RecursionError on a million. Whoever supplies the tree chooses its depth, so code that walks trees shaped by someone else keeps its own stack in a loop and refuses input deeper than a stated limit.

Trees You Already Walk

The file system is a tree of names leading to directories and files, and Chapter 10 shows how it is stored. A browser turns every page of HTML into a tree of elements before it draws anything. A service that accepts JSON parses every request body into a tree of objects and lists. And every compiler and interpreter turns source text into a syntax tree, the subject of Chapter 13.

A syntax tree is evaluated in post-order, and that order is what makes arithmetic come out right. In two times the sum of three and four, the multiplication sits at the root with the sum below it. Post-order reaches the leaves first, then the addition, which produces seven, and only then the multiplication, which produces fourteen. The order of evaluation is not a rule the interpreter looks up; it is the shape of the tree walked children first.

The Cost in a System You Run

A walk touches every node, so its price is the number of nodes times the price of reaching one node. In memory, one step is a pointer hop, and each hop to a node the processor has not touched recently can be a cache miss of about 100 nanoseconds, the RAM row of the latency ladder in Chapter 4. On disk, one step is a metadata read per file.

So a backup or build tool that walks a dependency folder of a million files is slow before it does any real work. On a cold cache, a million metadata reads at the slow end of the SSD row, about 100 microseconds each, add up to about 100 seconds. On a warm cache, where the kernel already holds that metadata in memory, the same walk drops to seconds. Neither figure depends on what the tool does with each file.

The cheapest node is the one never visited. A walk that can decide at a folder that nothing inside it matters, a build tool skipping a directory it knows is unchanged, a search skipping a subtree whose name rules it out, saves every node below that point. Pruning at the root of a subtree is the one optimization that changes the count instead of the price per node.