Binary Tree Traversal

Traversing a binary tree

Traversal is a linear operation. Traversing an array or linked list, which already has a linear structure, is straightforward.

A binary tree is nonlinear. Traversal converts its linked nodes into a linear sequence, and different traversal rules produce different sequences.

There are four traversal orders:

1. Preorder: visit the root, traverse the left subtree, then the right subtree.

2. Inorder: traverse the left subtree, visit the root, then traverse the right subtree.

3. Postorder: traverse the left subtree, traverse the right subtree, then visit the root.

4. Level order: traverse horizontally, one level at a time, from the root toward the leaves.

The code uses each node’s data, left, and right fields. Place the Java Node and traversal methods in the same enclosing class. The C iterative inorder and level-order routines take the total node count n to allocate a pointer stack or queue.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_t {
    int data;
    struct node_t *left;
    struct node_t *right;
} node_t;

Preorder

Visit the root first, then traverse the left subtree and finally the right subtree. Apply the same root–left–right rule recursively to each subtree. Return when the node is null.

Preorder

void pre_order(node_t *node) {
    if (node == NULL) {
        return;
    }
    printf("%d\n", node->data);
    pre_order(node->left);
    pre_order(node->right);
}

Inorder

Traverse the left subtree first, visit the root, and finally traverse the right subtree. Return when the node is null.

Inorder

void in_order(node_t *node) {
    if (node == NULL) {
        return;
    }
    in_order(node->left);
    printf("%d\n", node->data);
    in_order(node->right);
}

Postorder

Traverse the left subtree, then the right subtree, and finally visit the root. Return when the node is null.

Postorder

void post_order(node_t *node) {
    if (node == NULL) {
        return;
    }
    post_order(node->left);
    post_order(node->right);
    printf("%d\n", node->data);
}

Iterative traversal

Most problems solved recursively can also be solved using a stack, because both support backtracking.

For inorder traversal, push a node onto the stack and follow its left subtree. When the left subtree is complete, pop and visit the top node, then follow its right pointer to traverse its right subtree.

Iterative inorder

void in_order_iterative(node_t *node, size_t n) {
    if (node == NULL) {
        return;
    }
    node_t **stack = malloc(n * sizeof(node_t *));
    if (stack == NULL) {
        fprintf(stderr, "Error: memory allocation failed.\n");
        return;
    }
    size_t top = 0;
    while (node != NULL || top > 0) {
        while (node != NULL) {
            stack[top++] = node;
            node = node->left;
        }
        node = stack[--top];
        printf("%d\n", node->data);
        node = node->right;
    }
    free(stack);
}

Level order

Nodes on the same level have no direct links between them. A queue provides the needed coordination.

Start by enqueuing the root. Until the queue is empty, dequeue a node, visit it, and enqueue its left and right children.

Level order

void level_order(node_t *node, size_t n) {
    if (node == NULL) {
        return;
    }
    node_t **queue = malloc(n * sizeof(node_t *));
    if (queue == NULL) {
        fprintf(stderr, "Error: memory allocation failed.\n");
        return;
    }
    size_t front = 0, rear = 0;
    queue[rear++] = node;
    while (front < rear) {
        node = queue[front++];
        printf("%d\n", node->data);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
    free(queue);
}