Tree traversals

How do you print every key of a tree, each exactly once? One short recursive function does it. Watch where it prints.

⋯20void preorder(const struct tnode *t)21{22    if (t == NULL)23        return;24    printf("%d ", t->key);25    preorder(t->left);26    preorder(t->right);27}⋯94    printf("preorder: ");95    preorder(root);96    printf("\ninorder: ");97    inorder(root);98    printf("\npostorder: ");99    postorder(root);100    printf("\n");

preorder: 

One route, three moments

Here is the walk the clip plays:

void preorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    printf("%d ", t->key);
    preorder(t->left);
    preorder(t->right);
}

It says: an empty tree has nothing to print; otherwise print this node, then walk the left subtree the same way, then the right. The function calls itself, which is recursion: each call handles one node and hands its two subtrees to two more calls of itself. The calls on NULL are where it stops.

Follow the cards. preorder(50) prints 50 and calls preorder(30), which prints 30 and calls preorder(20), which prints 20 and calls preorder(NULL) for 20’s left child. That call returns at once, and so does the one for 20’s right child, and preorder(20) is done. Its card goes, and the walk is back in preorder(30), which now calls preorder(40). At any moment the cards are the path from the root down to the node the walk is at: 50, 30, 20 when it is at 20.

Now the marker. Picture a line drawn tight round the outside of the tree, starting on the left of the root. It passes each node three times: on its left as the call on that node begins, underneath it once the left subtree is done, and on its right once both subtrees are done. The three walks follow exactly this route. They differ only in where they print:

• Preorder prints a node as the marker passes its left, before either subtree: 50 30 20 40 70 60 80.
• Inorder prints it underneath, between the two subtrees: 20 30 40 50 60 70 80.
• Postorder prints it on its right, after both: 20 40 30 60 80 70 50.

Switch “Order” to inorder and watch it again: the cards and the marker make the same moves, and only the moments the row fills are different. Then postorder.

The inorder line comes out sorted. That is the rule of a binary search tree at work: everything in a node’s left subtree is smaller and everything in its right subtree larger, so printing the left subtree, then the node, then the right subtree prints the keys in increasing order. That is the promise made in Binary search trees.

The code and its cost

The three walks

void inorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    inorder(t->left);
    printf("%d ", t->key);
    inorder(t->right);
}

void postorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    postorder(t->left);
    postorder(t->right);
    printf("%d ", t->key);
}

The bodies are the same three lines in a different order. The printf moves; the two calls stay where they are.

What it costs

Each walk makes one call for every node and one for every empty child. A tree of n nodes has n + 1 NULL pointers (Binary trees, 12.1), so a walk makes n + (n + 1) = 2n + 1 calls: 15 for the house tree’s 7 nodes, which is what the “calls” readout ends on. Each call does a fixed amount of work, so the walk takes a number of steps proportional to n.

The stack holds one card per call that has not returned, and those calls are the path from the root to where the walk is, plus one call on NULL at the bottom. So the stack is as deep as the tree’s height plus two: here 2 + 2 = 4 cards (50, 30, 20 and an empty child), the most the clip shows. A tree of a million nodes with every level full but the last has height 19, and its walk is at most 21 cards deep; a chain of a million nodes would need a million and one. Traversals with a stack or a queue walks a tree with no recursion at all.

Measuring a tree the same way

The same pattern answers questions about a tree: find the answer for each subtree, then combine them.

int count(const struct tnode *t)
{
    if (t == NULL)
        return 0;
    int l = count(t->left);
    int r = count(t->right);
    return 1 + l + r;
}

int height(const struct tnode *t)
{
    if (t == NULL)
        return -1;
    int l = height(t->left);
    int r = height(t->right);
    return 1 + (l > r ? l : r);
}

count adds 1 for the node to the counts of its two subtrees, and an empty tree has 0. height adds 1 to the taller subtree’s height, and an empty tree has height −1, so a single node gets 1 + (−1) = 0, as Binary trees defined it. leaves returns 1 at a node with no children and adds up the two sides elsewhere. On the house tree the program prints count 7, height 2, leaves 4. These are postorder walks: each node’s answer is ready only after both of its subtrees have answered.

Which order for which job

• Freeing a tree: postorder. A node is freed after both its subtrees, so its pointers are still there to follow when they are needed. free_tree in the program is a postorder walk; it frees 20, 40, 30, 60, 80, 70 and then 50.
• Copying a tree: preorder. Make the copy of a node first, then copy its subtrees and hang them under it.
• Printing an expression. The three orders of an expression tree are its three written forms, prefix, infix and postfix: the worked example below, and Infix to postfix.

Running it yourself

The code pane shows one walk and the lines of main that call the three. The full program, traversals.c, has the struct, make (which takes a key and the two children, so main builds the tree from its leaves up: 20, 40, then 30 over them, and so on), the three walks, count, height, leaves, free_tree and main. Build and run it with:

gcc -std=c11 -Wall -Wextra -pedantic traversals.c -o traversals
./traversals

Worked example

Rebuilding a tree from two walks. A tree has preorder 1 2 4 5 3 6 and inorder 4 2 5 1 6 3. What is it?

The first preorder key is always the root: 1. In the inorder list, everything left of 1 is in its left subtree and everything right of it in its right subtree: 4 2 5 on the left, 6 3 on the right. The preorder list keeps the subtrees together too: after the root come the left subtree’s three keys, 2 4 5, then the right’s, 3 6.

Now do the same for each side. The left part has preorder 2 4 5 and inorder 4 2 5: root 2, with 4 on its left and 5 on its right. The right part has preorder 3 6 and inorder 6 3: root 3, and 6 is left of 3 in the inorder list, so 6 is 3’s left child.

        1
       / \
      2   3
     / \  /
    4  5 6

Its postorder is 4 5 2 6 3 1. The program rebuild.c does exactly this with a recursive rebuild(pre, in, n): it finds the root’s place k in in, rebuilds the left side from the next k keys of pre and the first k of in, the right side from the rest, and calls make on the root with the two. Run on these lists, it prints 4 5 2 6 3 1. Preorder alone would not do: 1 2 3, for example, is the preorder of a chain going left, a chain going right, and three other shapes.

An expression tree. The expression (8 − 2) × 3 is the tree with × at the root, the subtree of 8 − 2 on its left, and 3 on its right.

       ×
      / \
     −   3
    / \
   8   2

The inorder line reads as 8 − 6 if you calculate it with the usual rules, so an infix printer must add brackets around every subtree to keep the meaning. The postorder line needs none: Evaluating postfix computes it with one stack, and gets 18.

Two checks. What is the inorder walk of any binary search tree? (Its keys in increasing order.) How many calls does a walk make on a tree of 100 nodes? (201: 100 nodes and 101 empty children.)

Where it’s used

Freeing and copying linked trees. Every program that builds a tree from malloced nodes frees it with a postorder walk, and copies it with a preorder one.

Directory listings. A listing that shows each folder and then, indented, what is inside it, is a preorder walk of the folder tree.

Evaluating expressions. A calculator or compiler that holds an expression as a tree evaluates it in postorder: both operands first, then the operator.

Keys in order. An inorder walk lists a search tree’s keys sorted, which is how ordered maps hand back their keys one by one.

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.