Binary trees

Five nodes on the heap, each with two pointers. What shape do they make? Watch the same arrows turn into a tree.

1#include <stdio.h>2#include <stdlib.h>3 4struct tnode {5    int key;6    struct tnode *left, *right;7};8 9struct tnode *new_node(int key)10{11    struct tnode *n = malloc(sizeof *n);12    if (n == NULL)13        exit(1);14    n->key = key;15    n->left = NULL;16    n->right = NULL;17    return n;18}19 20int main(void)21{22    struct tnode *d = new_node(4);23    struct tnode *b = new_node(2);24    struct tnode *e = new_node(5);25    struct tnode *a = new_node(1);26    struct tnode *c = new_node(3);27    a->left = b;28    a->right = c;29    b->left = d;30    b->right = e;31    printf("root %d, children %d and %d\n", a->key, a->left->key, a->right->key);32    free(d);33    free(e);34    free(b);35    free(c);36    free(a);37    return 0;38}

Five nodes, four arrows

The program makes five nodes with new_node, the function you met in Binary search trees: each call asks malloc for one node, writes its key and sets both of its pointers to NULL. The keys are made in the order 4, 2, 5, 1, 3, and the heap places the blocks one after another in that order, from 0x1000 to 0x1080. In memory there is no shape at all: just five boxes in a row, in the order they were asked for.

Then four lines join them:

a->left = b;
a->right = c;
b->left = d;
b->right = e;

Each line writes one address into one pointer, and each draws one arrow. The node for 1 now points to 2 and 3, and the node for 2 points to 4 and 5. The arrows cross the row in every direction, because the order on the heap has nothing to do with who points to whom.

Then the picture redraws the same five boxes and the same four arrows: 1 at the top, the nodes it points to below it, the nodes they point to below them. Nothing in memory changes during the glide. Every address under every box is the one it had in the row, and no byte is written. That drawing, with each node above the nodes it points to, is a binary tree: each node points to at most two others, its children, and every node except one is pointed to by exactly one parent.

printf then follows the pointers from the top: a->key is 1, a->left->key is 2 and a->right->key is 3, so it prints root 1, children 2 and 3. Last, the program frees the nodes, the two at the bottom first, then 2, then 3, then 1. A node is freed only after both of its children, so no node is freed while it still holds the only pointer to a node that has not been freed yet. Tree traversals frees a whole tree that way with one short function.

The code and its cost

The words

Here is the tree from the clip, with its keys:

        1
       / \
      2   3
     / \
    4   5

• The root is the one node with no parent: 1. A program keeps a pointer to it, here a, and reaches every other node from there.
• A node’s children are the nodes its two pointers point to; it is their parent. 2 and 3 are the children of 1, and 1 is their parent.
• A leaf is a node with no children: 4, 5 and 3.
• A node’s subtree is the node with everything below it. The subtree of 2 is 2, 4 and 5; it is the root’s left subtree, and the subtree of 3 is the right one.
• The depth of a node counts the edges from the root down to it: 1 has depth 0, 2 and 3 have depth 1, 4 and 5 depth 2.
• The height of a tree is the largest depth of any node, so this tree has height 2. Height counts edges, not nodes: a single node has height 0, and an empty tree, by agreement, height −1.

The node

struct tnode {
    int key;
    struct tnode *left, *right;
};

This is the struct of Binary search trees, and it is 24 bytes here: key at 0, 4 bytes of padding, left at 8 and right at 16. A missing child is a NULL pointer, drawn as a hollow dot. A leaf has two of them, so not every node has two children; every node has two pointers.

Count the pointers in the clip’s tree: five nodes have ten, four of them are arrows, and six are NULL. That holds for any binary tree: every node but the root has one arrow coming in, so n nodes have n − 1 arrows, and the other 2n − (n − 1) = n + 1 pointers are NULL.

How tall, how full

Each level of a binary tree can hold at most twice as many nodes as the level above it: 1 at depth 0, 2 at depth 1, 4 at depth 2, and 2ᵈ at depth d. So a tree of height h holds at most

nodes. Turn that round: to hold n nodes, a tree needs $2^{h+1} - 1 \ge n$, so its height is at least ⌊log₂ n⌋. For the clip’s five nodes that is ⌊log₂ 5⌋ = 2, the height they have. The other extreme is a chain, each node with one child, and its height is n − 1.

This is the number that matters later. Every search tree in this part of the course walks one path from the root, so its cost is its height, somewhere between about log₂ n and n − 1.

Full, complete and perfect

Three names describe how well a tree is filled:

• Full: every node has 0 or 2 children, never 1.
• Complete: every level is full except possibly the last, and the last is filled from the left with no gaps.
• Perfect: every level is full. A perfect tree of height h has exactly $2^{h+1} - 1$ nodes.

The clip’s tree is full (1 and 2 have two children each, the rest none) and complete (levels 0 and 1 are full, and the last level holds 4 and 5 at its left). It is not perfect: a perfect tree of height 2 has 7 nodes, and this one has 5. Complete trees come back in Storing trees, where they fit an array without gaps, and in Binary heaps (14.1).

How many shapes

How many different binary trees can five nodes make, if only the shape counts? Watch the shapes for 1, 2, 3 and 4 nodes first.

The counts come from one idea. Pick how many of the other n − 1 nodes go into the root’s left subtree, say k; the rest go right. The number of shapes is the number of left shapes times the number of right shapes, added up over every k. For 4 nodes, the left subtree holds 0, 1, 2 or 3 of the other three, which gives 1 × 5 + 1 × 2 + 2 × 1 + 5 × 1 = 14 (left shapes × right shapes, for k = 0 to 3). These are the Catalan numbers, and they have a formula:

with the binomial coefficient of Counting. They grow fast: 42 for 5 nodes, and 16,796 for 10.

Worked example

The words on the clip’s tree. Depths: 1 at 0; 2 and 3 at 1; 4 and 5 at 2. Height 2. Leaves 4, 5 and 3. Full and complete, not perfect. Six NULL pointers, which is n + 1 for n = 5.

The most nodes for a height. $2^{h+1} - 1$ gives:

So a tree only 19 edges tall can hold over a million nodes, and a search that walks one path from its root looks at no more than 20 of them.

The least height for 1,000 nodes. Height 9 holds at most $2^{10} - 1$ = 1,023 nodes, which is enough; height 8 holds at most $2^9 - 1$ = 511, which is not. So 1,000 nodes need a height of at least 9, and ⌊log₂ 1000⌋ = 9 says the same.

Shapes, by the formula. For 3 nodes, C(6, 3)/4 = 20/4 = 5. For 4, C(8, 4)/5 = 70/5 = 14. For 5, C(10, 5)/6 = 252/6 = 42. The same numbers as the picture.

Three checks before you move on. A chain of 5 nodes has what height? (4: it has 4 edges.) Can a tree of height 2 hold 8 nodes? (No: at most 7.) And is the clip’s tree a binary search tree? (No: 4 and 5 sit in the left subtree of 2, but 5 is larger than 2. A binary search tree is a binary tree with an extra rule about its keys: Binary search trees.)

Where it’s used

Compilers. A compiler turns (8 - 2) * 3 into an expression tree: * at the root, with the tree of 8 - 2 on its left and 3 on its right. Each operator node has two children, its operands.

Decision trees. A decision tree in machine learning asks a yes-or-no question at each node and goes to one of two children: Decision trees.

Folders. A file system’s folders form a tree, though a folder can have any number of children; Storing trees shows how such a tree is stored in nodes with two pointers.

The rest of this part. Search trees (Chapter 13) add a rule about where keys go, and heaps (Chapter 14) add a different one. Both are binary trees first.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.