Traversals with a stack or a queue

Walk a tree with no recursion: hold the nodes still to visit in a container. Watch the order a stack gives, then a queue.

⋯29#define CAP 1630 31void walk_stack(struct tnode *root)32{33    struct tnode *stack[CAP];34    int top = 0;35    stack[top++] = root;36    while (top > 0) {37        struct tnode *t = stack[--top];38        printf("%d ", t->key);39        if (t->right != NULL)40            stack[top++] = t->right;41        if (t->left != NULL)42            stack[top++] = t->left;43    }44    printf("\n");45}⋯89    walk_stack(root);90    walk_queue(root);91    inorder_stack(root);

Take one, visit it, put its children in

Tree traversals walked the tree with recursion: each call handled a node and left its unfinished business on the call stack. Here the program keeps that business itself, in an array:

void walk_stack(struct tnode *root)
{
    struct tnode *stack[CAP];
    int top = 0;
    stack[top++] = root;
    while (top > 0) {
        struct tnode *t = stack[--top];
        printf("%d ", t->key);
        if (t->right != NULL)
            stack[top++] = t->right;
        if (t->left != NULL)
            stack[top++] = t->left;
    }
    printf("\n");
}

The loop says: take a node out, visit it, put its children in; repeat until the container is empty. The container here is a stack of node pointers, the array and top index of Stacks, with top the number of pointers on it.

Follow the clip. The stack starts holding the root, 50. The loop pops it and prints 50, then pushes 70 (the right child) and 30 (the left), so 30 is on top. It pops 30, prints it, and pushes 40 and 20. It pops 20 and prints it. 20 has no children, so nothing goes in, and the next pop brings out 40, then 70, which pushes 80 and 60. The order is 50 30 20 40 70 60 80: the preorder of Tree traversals, with no function calling itself.

The right child goes in first so that the left one comes out first: a stack hands back the last thing put in. Push them the other way round and the walk would print 50 70 80 60 30 40 20, the mirror image.

Now set “Container” to queue.

void walk_queue(struct tnode *root)
{
    struct tnode *queue[CAP];
    int head = 0, tail = 0;
    queue[tail++] = root;
    while (head < tail) {
        struct tnode *t = queue[head++];
        printf("%d ", t->key);
        if (t->left != NULL)
            queue[tail++] = t->left;
        if (t->right != NULL)
            queue[tail++] = t->right;
    }
    printf("\n");
}

The loop is the same: take one out, visit it, put its children in. A queue hands things back in the order they went in, first in, first out. New pointers join at tail, and the next one taken is the one at head. The left child now goes in first, because it should come out first.

The queue starts holding 50. The loop takes 50 and adds 30 and 70. It takes 30 and adds 20 and 40 behind 70; it takes 70 and adds 60 and 80 behind those. Then it takes 20, 40, 60 and 80, which add nothing. The order is 50 30 70 20 40 60 80: the root, then every node one level down, then every node two levels down. This is level order, also called breadth first, and recursion does not give it.

The code and its cost

Why the two orders differ

A stack always works on the newest node it holds, so after visiting a node it goes straight on to that node’s left child, then that child’s left child, as deep as the tree goes, before it comes back for the right children it left waiting. That is depth-first order, the same as the recursive preorder; the stack holds what the call stack held.

A queue works on the oldest node it holds. Every node of one level went in before any of their children, so all of them come out before any of their children do. That is breadth-first order.

What it costs

Each node goes into the container once and comes out once, and each visit does a fixed amount of work, so either loop takes a number of steps proportional to n, as the recursive walks did.

The space is different. The stack holds about one waiting right child per level on the way down, so its size is at most about the height: 3 here, the most the clip’s readout shows. The queue holds up to a whole level at once: 4 here, when 20, 40, 60 and 80 are all waiting.

Neither loop calls itself, so neither can run out of call stack on a deep tree. A chain of a million nodes would make the recursive walk a million calls deep; walk_stack on the same chain never holds more than one pointer, because each node pushes only its single child after it has been popped.

The array sizes

CAP is 16, which is plenty for a tree of seven nodes: the queue’s tail never gets past 7. A real program sizes the stack from the tree’s height and the queue from its widest level, or uses arrays that grow. The queue here never needs to wrap round, because 7 nodes go through 16 cells. A queue that is reused, where head and tail chase each other round the array, is the ring buffer of Queues (9.2).

Inorder with a stack

Inorder prints a node between its subtrees, so a node can’t simply be visited when it comes off the stack. The loop is a little different:

void inorder_stack(struct tnode *root)
{
    struct tnode *stack[CAP];
    int top = 0;
    struct tnode *cur = root;
    while (cur != NULL || top > 0) {
        while (cur != NULL) {
            stack[top++] = cur;
            cur = cur->left;
        }
        cur = stack[--top];
        printf("%d ", cur->key);
        cur = cur->right;
    }
    printf("\n");
}

Go left as far as possible, pushing each node on the way. Pop one and print it. Then go right, and start again. A node waits on the stack while its left subtree is printed, which is exactly when inorder wants it. The program prints 20 30 40 50 60 70 80.

Running it yourself

The full program, walks.c, starts with the includes, struct tnode, make and free_tree copied from traversals.c (Tree traversals), then the three loops and a main that builds the house tree and calls them in turn. Build and run it with:

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

Worked example

The most each container holds. On the house tree, the stack never holds more than 3 pointers (70 40 20, after 30’s visit) and the queue never more than 4 (20 40 60 80, after 70’s).

A bigger tree. Take a perfect tree of height 9: 1,023 nodes, ten levels. The stack version holds at most 10 pointers, one waiting right child for each level it has gone down plus the left child on top. The queue version must at some moment hold the whole last level: 2⁹ = 512 pointers. For trees like this one, the stack is the far smaller container.

Iterative inorder, step by step. On the house tree:

Two checks. If walk_stack pushed the left child before the right, what would it print? (50 70 80 60 30 40 20: preorder of the mirrored tree.) Which container finds the shallowest leaf first? (The queue: it reaches every node of one level before any of the next.)

Where it’s used

Very deep trees. A tree built from data you don’t control, such as a parse of nested input, can be far deeper than the call stack allows. A loop with its own stack walks it safely.

Printing a tree level by level. Showing a tree on screen row by row, or finding everything within two steps of the root, is a level-order walk with a queue.

Graphs. The same two loops, with a mark so that no node is visited twice, are depth-first and breadth-first search on graphs, in the graph chapter (19.2 and 19.3).

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.