Binary tree postorder traversal in C: solved exercise

Binary tree postorder traversal in C: solved exercise

If you searched for a solved postorder traversal of a binary tree in C, here are the recursive and two-stack iterative versions. Postorder visits nodes in the order left child → right child → root (LRN), making it the natural traversal for freeing a tree’s memory.

The iterative postorder is more complex than iterative preorder because the root is processed last; the two-stack trick reverses the right-first preorder to obtain postorder.

Problem statement

Given the tree:

1
2
3
4
5

        1
       / \
      2   3
     / \   \
    4   5   6

Print the nodes in postorder 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
61

#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 postorder_rec(const Node *n) {
    if (!n) return;
    postorder_rec(n->left);
    postorder_rec(n->right);
    printf("%d ", n->data);
}

/* --- Iterative version with two stacks --- */
#define MAX 64
void postorder_iter(const Node *root) {
    if (!root) return;
    const Node *s1[MAX], *s2[MAX];
    int t1 = 0, t2 = 0;
    s1[t1++] = root;

    while (t1 > 0) {
        const Node *n = s1[--t1];
        s2[t2++] = n;                    /* reversed result */
        if (n->left)  s1[t1++] = n->left;
        if (n->right) s1[t1++] = n->right;
    }
    /* Drain second stack = postorder */
    while (t2 > 0) printf("%d ", s2[--t2]->data);
}

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: "); postorder_rec(root);  printf("\n");
    printf("Iterative: "); postorder_iter(root); printf("\n");

    free_tree(root);
    return 0;
}

Expected output

1
2

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

Common mistakes

  • Trying to use a single stack without a tracking pointer: possible but requires an extra variable to track the last visited node, making the implementation harder. Two stacks are clearer.
  • Getting the LRN order wrong: swapping the children gives RLN — a mirrored traversal.
  • Freeing memory in preorder instead of postorder: freeing a node before its children leaves dangling pointers and prevents reaching the children.
  • Using int as the stack element type instead of Node *: the stack must store node pointers.

Practical use

Postorder is used to free tree memory (children must be freed before the parent), to evaluate postfix (RPN) expressions, to compute subdirectory sizes in a file system tree, and in compiler code generation (operands are evaluated before the operator).

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Why does the iterative postorder need two stacks?

Because postorder processes the root last, which is contrary to a LIFO stack’s natural behavior. The trick is to perform a preorder-like traversal visiting the right child first (root-right-left), store nodes in a second stack, and then draining it gives the reverse order: left-right-root = postorder.

How can you tell if a traversal is in postorder without running the code?

For the exercise tree: leaf nodes (4, 5, 6) always appear before their parents (2, 3), and the root (1) always appears last. If the last element is the root and children always precede their parents, the traversal is postorder.

Can postorder be implemented with a single stack?

Yes, by maintaining a last_visited pointer tracking the most recently processed node. When the right child has already been visited (or does not exist), the root is processed. The logic is more complex; two stacks are preferable for clarity.