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

In Chapter 55 we flattened a grid into one straight line of memory. 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. Think of 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. The whole way through we keep asking the one question that decides everything downstream. 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 lightning and disaster. 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 let's 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; 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.

Make it concrete with the little tree we'll carry all chapter: A at the top, with children B and C. B holds D and E, and C holds only a right child, F. So A is the root, and its depth is 0. D, E, and F are leaves, because none of them has a child. B is the parent of D and E, and the edge from A to B is one hop down. Notice that C has a right child but no left one. That empty left slot is real, and the position is part of the data. That is exactly why left and right are not interchangeable.

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

Why does “the definition contains itself” matter so much? It means every question about a tree has the same shape as a question about a smaller tree. Ask for the height of A, and the answer is one more than the taller of B's tree and C's tree. Ask for the node count, and it is one plus the count on the left plus the count on the right. The no-cycles rule is what keeps this recursion from ever looping forever. Because there is exactly one path from the root to any node, walking down can never circle back to a box you have already visited. You always shrink toward the empty tree, so you always stop.

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.

One number per arrow — that is the whole trick. A reference is just an address, the 8-byte number of where a box sits in RAM. When node A stores its left child, it is not holding B inside itself; it is holding B's address, a single integer like 0x7f3a…. Follow that integer and the machine loads the bytes parked there, and now you are standing on B. The hierarchy you picture as a shape is, underneath, nothing but a handful of these addresses pointing at one another. Lose the addresses and the boxes are just unrelated litter on the heap.

How heavy is one node? The honest answer is to measure, not guess, and the machine will tell us exactly what it costs. We give the class __slots__ so its three fields pack straight into the object, and each node becomes a lean record with no room left for hidden weight.

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. The tree is roughly 7× heavier. A tree is not a light structure. You buy shape with bytes.

Put real numbers on our six-node tree, then. Slotted, it is 6 × 56 = 336 bytes of node objects, plus the one 8-byte name that holds the root. Drop __slots__ and those same six nodes swell to 6 × 344 = 2,064 bytes, more than six times the memory for the identical shape. That gap is pure overhead — not one extra value stored, just the instance __dict__ that __slots__ deletes. On a tree of a million nodes the same multiplier turns roughly 56 MB into 344 MB. The pointer tax you cannot avoid; the dictionary tax is a choice you get to decline.

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, and here is exactly 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 is 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.

Make that cost concrete on our little tree. To reach leaf F, you start at the root A, follow one child pointer down to C, then one more to F: two hops, exactly its depth. There is no index to jump with and no shortcut to take — the only way down is to follow the pointers, one level at a time. So the deepest node fixes the worst case, and the worst case is the height. That is all O(height) is really saying: the work is a walk, and the walk is as long as the tree is tall.

That turns the whole question into one line: how tall does n nodes have to stack? There are two answers, and they could not sit further apart. The very same node count can give you a shape that flies or a shape that crawls.

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 — 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; of 1,000,000 nodes, height 19. Nineteen hops to reach any node among a million.

Let's check that height-19 claim by hand, because it is the whole promise of the shape. A completely filled tree of height h holds up to 2^h+1−1 nodes. Height 9 gives 2¹⁰−1 = 1,023 nodes, so 1,000 items fit with a level to spare. Height 19 gives 2²⁰−1 = 1,048,575 nodes, just past a million. So a million items really do sit within 19 hops of the root. Add one more level, height 20, and you have room for over two million. Each level you add doubles the reach, which is exactly what log₂n means read backwards.

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, so 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 is the same linked list we built a few chapters back, wearing a tree costume, and every search is O(n).

Watch it happen with five values. Insert 1, then 2: two is larger, so it hangs to the right of one. Insert 3, and it slides past one and two to the right again; 4 and 5 do the same thing. What you are left with is the chain 1→2→3→4→5, a spine of height 4, which is exactly n−1 for five nodes. Now search for 5 and you must step through all four nodes stacked above it. Five sorted values already cost four hops, and a thousand would cost 999 — the linked list wearing its tree costume.

So the same n nodes can cost 9 hops or 999, and nothing about being “a tree” decides which. The order you insert in does. Feed a balanced shape and you get log-depth. Feed already-sorted data into a naive tree and you get the spine. This is the crack that the whole rest of the volume is built to seal. The self-balancing trees ahead notice when one side grows too tall and quietly rotate nodes to keep the height near log n. For now, just hold the tension: height is earned, not guaranteed.

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. The node count is the same O(n) as a list scan, but the real speed is wildly different. The exponent ties, and 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. There are no loops and no manual bookkeeping. Here, 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

Line 2–3 is the floor: an empty tree contributes −1, so that 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.

Walk it once on our tree to feel the shrink. Call height(A). It needs its taller subtree, so it calls height(B) and height(C). height(B) asks its children D and E, both leaves, and each returns 0, so B returns 1. height(C) has an empty left that returns −1 and a leaf F on the right that returns 0, so C also returns 1. Back at A, the taller of 1 and 1 is 1, plus its own edge, gives 2. The call stack was never deeper than the path A→B→D, three nodes. On a spine it would have been as deep as the tree is tall.

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, and 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 — 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, and 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 is the walk you want when “closest to the root” means “most important.”

Trace that queue on our tree and the order falls straight out. Start by visiting A and enqueueing its children, so the queue holds [B, C]. Pop B, visit it, and push D and E, which leaves [C, D, E]. Pop C, visit it, and push its lone child F, which leaves [D, E, F]. From here every pop is a leaf with nothing to add, so you drain D, E, and F in turn. The visit order is A B C D E F, top level first and each level left to right — precisely what a queue's first-in-first-out discipline buys you.

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, pulling from the front and pushing children to the back. 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.

INPUTfrom collections import deque

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

def pre(n):                       # touch the node BEFORE both descents
    if n is None: return
    yield n.value
    yield from pre(n.left)
    yield from pre(n.right)

def ino(n):                       # touch it BETWEEN the two descents
    if n is None: return
    yield from ino(n.left)
    yield n.value
    yield from ino(n.right)

def post(n):                      # touch it AFTER both descents
    if n is None: return
    yield from post(n.left)
    yield from post(n.right)
    yield n.value

def level(root):                  # breadth-first: a queue, not the call stack
    q = deque([root])
    while q:
        n = q.popleft()
        yield n.value
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)

tree = Node('A', Node('B', Node('D'), Node('E')), Node('C', None, Node('F')))

print("pre-order  :", ' '.join(pre(tree)))
print("in-order   :", ' '.join(ino(tree)))
print("post-order :", ' '.join(post(tree)))
print("level-order:", ' '.join(level(tree)))

walk = ino(tree)                  # a generator is LAZY: it walks only as far as asked
print("first two of in-order:", next(walk), next(walk))

g = pre(tree)                     # ...and one-shot: drained once, empty ever after
print("drain once :", list(g))
print("drain twice:", list(g))

OUTPUTpre-order  : A B D E C F
in-order   : D B E A C F
post-order : D E B F C A
level-order: A B C D E F
first two of in-order: D B
drain once : ['A', 'B', 'D', 'E', 'C', 'F']
drain twice: []

Each order is the right tool for a different job, and that is why all three survive. Pre-order touches a node before its children, so it is how you copy a tree or write it to a file: you emit the parent, then everything beneath it. Post-order touches a node after both children, so it is how you free or delete a tree safely, because you never remove a parent while its children still hang off it. In-order touches the left subtree, then the node, then the right. On the ordered trees of the next chapter, that single rule hands you every value in sorted order, for free.

Feel why post-order is the safe order to delete in. On our tree it visits D E B F C A, so you free D and E first, and only then their parent B. Next you free F, then its parent C, and the root A comes last of all. At no moment do you free a node while a child still points into it — every parent outlives its children by exactly one step. Reverse the order and you would free A while B and C still dangle, leaking the whole tree hanging beneath it. Here the order is the correctness, not a detail you can shrug off.

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. Then 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, with insert, find, and delete all in O(log n). A tree delivers that, but only while its height stays near log n. That “only while” is the entire craft. A bare binary tree gives you the shape, but 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, and you reach for a tree. Need ordered data with fast search, and it's a BST. Need the smallest or largest item again and again, and it's a heap. Need to look things up by prefix, and it's 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 single line, is the real skill. The code is the easy part that follows.

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

def count_leaves(node):
    """A leaf is a node with no children at all."""
    if node is None:                            # empty tree -> no leaves
        return 0
    if node.left is None and node.right is None:
        return 1                                # a leaf counts itself and stops
    return count_leaves(node.left) + count_leaves(node.right)

def count_nodes(node):
    if node is None: return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

def mirror(node):
    """Swap every left/right pair, top to bottom - in place."""
    if node is None:
        return None
    node.left, node.right = mirror(node.right), mirror(node.left)
    return node

def inorder(node, out):
    if node is None: return
    inorder(node.left, out); out.append(node.value); inorder(node.right, out)

def build():
    return Node('A', Node('B', Node('D'), Node('E')), Node('C', None, Node('F')))

def perfect(h, k=0):
    if h < 0: return None
    return Node(k, perfect(h - 1, 2*k + 1), perfect(h - 1, 2*k + 2))

t = build()
print("nodes      :", count_nodes(t))
print("leaves     :", count_leaves(t), "  (D, E, F)")
print("empty tree :", count_leaves(None))
print("lone node  :", count_leaves(Node('X')))

before = []; inorder(t, before)
mirror(t)
after = []; inorder(t, after)
print("\nin-order before mirror:", ' '.join(before))
print("in-order after  mirror:", ' '.join(after))
print("after == reversed(before)?", after == before[::-1])
print("leaves survive the mirror:", count_leaves(t))

mirror(t); again = []; inorder(t, again)          # a mirror is its own undo
print("mirror twice == original?", again == before)

print()
for h in range(5):
    p = perfect(h)
    print(f"perfect height {h}: nodes={count_nodes(p):3}  leaves={count_leaves(p):3}"
          f"  2**h={2**h:3}")

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# nodes      : 6
# leaves     : 3   (D, E, F)
# empty tree : 0
# lone node  : 1
#
# in-order before mirror: D B E A C F
# in-order after  mirror: F C A E B D
# after == reversed(before)? True
# leaves survive the mirror: 3
# mirror twice == original? True
#
# perfect height 0: nodes=  1  leaves=  1  2**h=  1
# perfect height 1: nodes=  3  leaves=  2  2**h=  2
# perfect height 2: nodes=  7  leaves=  4  2**h=  4
# perfect height 3: nodes= 15  leaves=  8  2**h=  8
# perfect height 4: nodes= 31  leaves= 16  2**h= 16

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. →