Binary tree preorder traversal in C: solved exercise

If you searched for a solved preorder traversal of a binary tree in C, here are the two canonical implementations: the recursive version (natural and concise) and the iterative version with an explicit stack (required for very deep trees that would exhaust the system stack).

In preorder, the visit order is root → left child → right child (NLR: Node-Left-Right).

Problem statement

Given the tree:

Print the nodes in preorder using both the recursive and iterative approaches.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node *new_node(int data) {
    Node *n = malloc(sizeof(Node));
    n->data = data; n->left = n->right = NULL;
    return n;
}

/* --- Recursive version --- */
void preorder_rec(const Node *n) {
    if (!n) return;
    printf("%d ", n->data);
    preorder_rec(n->left);
    preorder_rec(n->right);
}

/* --- Iterative version with stack --- */
#define MAX_STACK 64
void preorder_iter(const Node *root) {
    if (!root) return;
    const Node *stack[MAX_STACK];
    int top = 0;
    stack[top++] = root;

    while (top > 0) {
        const Node *n = stack[--top];
        printf("%d ", n->data);
        /* Push right first so left is processed first */
        if (n->right) stack[top++] = n->right;
        if (n->left)  stack[top++] = n->left;
    }
}

void free_tree(Node *n) {
    if (!n) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

int main(void) {
    Node *root    = new_node(1);
    root->left    = new_node(2);
    root->right   = new_node(3);
    root->left->left  = new_node(4);
    root->left->right = new_node(5);
    root->right->right = new_node(6);

    printf("Recursive: "); preorder_rec(root);  printf("\n");
    printf("Iterative: "); preorder_iter(root); printf("\n");

    free_tree(root);
    return 0;
}

Expected output

1
2
Recursive: 1 2 4 5 3 6 
Iterative: 1 2 4 5 3 6 

Common mistakes

In the iterative version, pushing the left child before the right: since the stack is LIFO, the right child must be pushed first so the left is processed first.
Not checking NULL before accessing children: n->left->data without verifying n->left != NULL causes a segmentation fault.
Not freeing tree memory: every node is allocated with malloc and must be freed with free by traversing the tree in postorder.
Confusing preorder with inorder: preorder visits the root first (NLR); inorder visits the root between the children (LNR).

Practical use

Preorder traversal is used to serialize/copy a tree (insertion order reconstructs the same structure), to evaluate expressions in prefix notation (expression trees), and to print a filesystem directory hierarchy.

Recommended next exercise

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

What is the difference between preorder, inorder, and postorder?

All three visit the same nodes but in different order:

Preorder (NLR): root first, then left subtree, then right subtree.
Inorder (LNR): left subtree, root, right subtree. Produces sorted values in a BST.
Postorder (LRN): subtrees first, root last. Useful for freeing memory.

When should I use the iterative version instead of the recursive one?

The recursive version is more readable and sufficient for trees of reasonable depth. The iterative version is necessary when the tree can be very deep (thousands of levels) and the system stack is insufficient. In production, self-balancing trees like AVL or Red-Black have O(log n) depth, making recursion safe.

Is the preorder traversal unique for a given tree?

Yes: for a given binary tree, the preorder sequence is unique. However, knowing only the preorder is not enough to reconstruct the tree; the inorder is also needed (or NULL nodes must be explicitly marked in the serialization).