56The binary tree — hierarchy, two children at a time

In Chapter 55 we flattened a grid into one straight line of memory, and that was the last easy one. Every structure so far has lived in a row: array, list, stack, queue, even the matrix, all of it laid end to end. A tree breaks the line. It's the shape of anything that contains things that contain things — a folder of folders, a web page of elements, a company of departments. Here we build the plainest one from its scattered bytes upward: the binary tree, one root, up to two children per node, no cycles. All the way through, one question decides everything else: if nowhere in RAM is there a thing shaped like a tree, what is actually holding the hierarchy together? By the end you'll see any hierarchy as nodes joined by two pointers. You'll know why a single number — its height — is the difference between a fast tree and one that crawls or crashes. And you'll be able to walk one four different ways, each for a different job.

01A tree is scattered boxes joined by pointers

Let's start with the vocabulary, and pin each word down the moment it lands. A node is one box holding a value. The single node at the top is the root. A node's children are the nodes hanging directly below it. That node is their parent, and the link between them is an edge. A node with no children is a leaf. Binary means each node has at most two children, and they are named: a left child and a right child. The position carries meaning, so left and right are not interchangeable. One rule makes it a tree and not a tangle: no cycles. There is exactly one path from the root down to any node.

The cleanest way to say all of that is to say it recursively: a binary tree is either empty, or it's a node holding a value plus two smaller binary trees (its left and right subtrees). The definition contains itself. Hold that thought. It's the whole reason trees are easy to walk.

Now the memory picture, which is this volume's obsession. Nowhere in RAM is there a thing shaped like a tree. On the heap a tree is a scatter of node objects. Each one is a tiny record with three fields: a reference to its value, a reference to its left child, and a reference to its right child (or None where a child is missing). The root is nothing but a name holding one 8-byte reference (Volume 1). Follow the left and right references from box to box and you are the tree. The shape exists only as pointers.

How heavy is one node? Let's measure, not guess. Give the class __slots__ so its three fields pack straight into the object, and each node becomes a lean record.

import sys

class Node:
    __slots__ = ('value', 'left', 'right')   # pack the 3 refs INTO the object — no per-instance dict
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left  = left
        self.right = right

root = Node('A', Node('B'), Node('C'))       # a 3-node tree, all on the heap
print(sys.getsizeof(root))                    # 56  → 16-byte header + three 8-byte references

Line 4 is the money line. __slots__ tells CPython to store value, left, and right inside the node itself, instead of in a separate instance dictionary. Ran on CPython 3.12.7, sys.getsizeof(root) returns 56 bytes: a 16-byte object header plus the three 8-byte references. Drop __slots__ and each node also drags a 296-byte instance __dict__ behind it, for 344 bytes per node, measured. Either way, that is the pointer tax. You pay two extra references per element (16 bytes) purely to encode the shape. Compare a Python list, a contiguous array of references (Volume 1): about 8 bytes per element plus one header. I measured 100,000 slotted nodes at 5,600,000 bytes against the same count in a list at 800,056 bytes, so the tree is roughly 7× heavier. A tree is not a light structure. You buy shape with bytes.

The answer isn't in the bytes. It's in one number that measures how tall the scatter of boxes stacks up — the tree's height. →

02Height is the whole game

Two more words, precisely. The depth of a node is how many edges you cross to reach it from the root (the root has depth 0). The height of a tree is the depth of its deepest node — the length of the longest root-to-leaf path. Height is the number that governs cost. Here's why: to reach any node, you start at the root and follow one child pointer per level down. So finding, inserting, or deleting a node costs O(height) pointer hops. It's never more than the height, because that's the longest any path can be. Derive the cost from the layout and it's forced: the work is the walk, and the walk is bounded by the height.

That turns the whole question into one: how tall does n nodes have to stack? There are two answers, and they could not be further apart.

Balanced. Fill the tree level by level and each level holds twice the one above: 1 root, then 2, then 4, then 8, …, 2^k at level k. So k levels hold up to 2^k+1−1 nodes. Invert that, and n nodes need only about log₂n levels. This is the same doubling that makes binary search O(log n) in Volume 3, now standing up in three dimensions. Measured: a balanced tree of 1,000 nodes has height 9, and of 1,000,000 nodes, height 19. Nineteen hops to reach any node among a million.

Degenerate. Now insert values already in sorted order into a tree that always sends the larger value right. Every node gets only a right child, and the tree collapses into a single diagonal spine. Its height is n−1: measured, 1,000 nodes give height 999. That is not a tree in any useful sense. It's the same linked list we built a few chapters back, wearing a tree costume, and every search is O(n).

To reach a node you followed pointers, one per level. But each pointer lands at a random address in RAM — and that randomness carries a cost that Big-O never prints on the label. →

03The pointer tax, paid again at runtime

A Python list is contiguous: element i lives at base + i·8, so scanning it streams whole cache lines the CPU prefetched (Volume 3's memory hierarchy). A tree's nodes were allocated one at a time, whenever you inserted them, so they sit at unrelated addresses. Look back at the memory diagram's scattered 0x7f… values. Walking the tree means chasing a pointer to a random location every single step. The prefetcher cannot guess where you'll jump next, so each hop risks a cache miss and a stall while the machine waits on RAM. It's the same O(n) node count as a list scan, but wildly different real speed. The exponent ties; the constant, set by the memory layout, decides.

Measured, and hedged as machine-dependent: summing a million values by walking a balanced tree in Python took about 312 ms on this machine. Summing the same million from a contiguous list in an equivalent Python loop took about 82 ms, roughly 3.8× faster. (The built-in sum(), running in C over that same packed array, did it in ~6.6 ms.) Part of the tree's penalty is the explicit stack and the attribute lookups; part is the cache misses of pointer-chasing. Both are the price of scatter, and both are invisible in the O(n) that the two share.

You can — and that exact trick is the secret of the heap, a couple of chapters ahead. But first: how do you visit every node at all, when the shape exists only as pointers? The structure hands you the tool. →

04Recursion is a tree's native tongue

Volume 3 taught recursion: solve a big problem by solving smaller versions of the same problem, down to a base case that needs no thought. A binary tree is that shape frozen into data — a node whose two children are themselves smaller trees. So the walk writes itself. To do something to a tree, handle this node, then recurse on the left subtree, then recurse on the right subtree. The base case is the empty tree (None), which needs no work at all. No loops, no manual bookkeeping: the data's self-similarity becomes the code's.

The smallest possible example is measuring the height itself:

def height(node):
    if node is None:          # BASE CASE: an empty tree is -1 edges tall
        return -1
    return 1 + max(height(node.left), height(node.right))   # 1 edge + the taller subtree

Lines 2–3 are the floor: an empty tree contributes −1, so a lone leaf (whose two children are empty) comes out to 0. Line 4 is the shrink: this node adds one edge on top of whichever subtree is taller, and each subtree is measured by the very same function on smaller data. It visits every node exactly once, so it is O(n). Ran on the six-node tree above, height returns 2, matching the diagram.

Notice the three moves inside every tree walk: touch this node, go left, go right. The only real decision is when you touch the node relative to the two descents — and that single choice spawns four different walks, each with a different job. →

05Four walks, four jobs

A traversal is a rule for visiting every node exactly once. Three of the four are depth-first: they plunge to the bottom before backing up. They differ only by where the “touch the node” step sits among the two recursive descents. Slide that one line and you get three orders:

• Pre-order (node · left · right): touch the parent before its children. You emit a folder before its contents, a parent before its subtree. That's perfect to serialize or copy a tree, because a reader rebuilds it top-down.
• In-order (left · node · right): touch the node between its subtrees. On an ordered tree (a BST — the very next chapter) this visits values in sorted order, the reason BSTs exist.
• Post-order (left · right · node): touch the parent after both children. You can't free a folder before its files, or add two numbers before you have them. So this is the order for deleting a tree and for evaluating an expression tree.

The fourth is breadth-first. Level-order abandons recursion for a queue (the structure from the queue chapter; this is exactly BFS from Volume 3): visit the root, enqueue its children, pop the next node, enqueue its children, and repeat. You sweep the tree one level at a time, nearest first. It's the walk you want when “closest to the root” means “most important.”

from collections import deque

def inorder(node, out):
    if node is None: return         # base case: empty subtree, nothing to do
    inorder(node.left, out)         # LEFT subtree first
    out.append(node.value)          # THEN this node
    inorder(node.right, out)        # THEN the RIGHT subtree
# pre-order: move the append ABOVE the two calls; post-order: move it BELOW both.

def levelorder(root):
    out, q = [], deque([root])      # a queue (Vol 1 deque) — this is BFS
    while q:
        node = q.popleft()          # take the shallowest waiting node
        out.append(node.value)
        if node.left:  q.append(node.left)    # its children go to the BACK
        if node.right: q.append(node.right)
    return out

The top function is the whole depth-first family. Those three lines, with append in the middle slot, are in-order. Lift it above both recursive calls and you have pre-order; drop it below both and you have post-order. The bottom function swaps the call stack for an explicit queue — pull from the front, push children to the back — and that single change turns depth-first into level-by-level. Ran on the six-node tree A(B(D,E), C(·,F)), CPython 3.12.7 gave exactly: in-order D B E A C F, pre-order A B D E C F, post-order D E B F C A, level-order A B C D E F.

Four walks and a two-pointer node: that's the entire general binary tree. Its power comes alive the moment you add one rule to the shape — and each rule you can add is a whole chapter. →

06When to reach for a tree

Strip everything away and a binary tree earns its keep in two situations. First, when your data is a hierarchy — a thing that contains things that contain things — the tree isn't a clever choice, it's the honest shape of the data: files, the DOM, an org chart. Second, when you need logarithmic reach — insert, find, and delete all in O(log n) — a tree delivers it, but only while its height stays near log n. That “only while” is the entire craft. A bare binary tree gives you the shape; it does not defend the balance. The specialized trees ahead each add exactly one rule to earn the log back and never let it slip.

That is the 1% move, and it is most of what being “good at data structures” actually is: match the access pattern to the layout. See a hierarchy → a tree. Need ordered data with fast search → a BST. Need the smallest (or largest) item again and again → a heap. Need to look things up by prefix → a trie. All four are this chapter's node-with-two-pointers wearing one extra discipline. Choosing the right discipline on sight — before you write a line — is the skill; the code is the easy part that follows.

Next — the binary search tree: add a single rule to the shape you just learned — every value in the left subtree smaller than the node, every value on the right larger. Suddenly the in-order walk prints in sorted order for free, and finding a value becomes binary search running on a tree. That is the binary search tree — and the whole fight to keep it from degenerating into the spine you met here. →