C Program for Postorder Traversal of Binary Tree

A C program for postorder traversal uses a recursive function that first visits the left subtree, then the right subtree, and finally processes the root node, like void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); }}.

Examples

InputTree: 1 (root), 2 (left child), 3 (right child)

Output2 3 1

InputTree: 10 (root), 20 (left child), 30 (right child), 40 (left child of 20)

Output40 20 30 10

InputEmpty tree (root = NULL)

Output

How to Think About It

To do postorder traversal, think of visiting the left side of the tree first, then the right side, and finally the node itself. This means you go deep to the leftmost node, then right nodes, and only then print the current node's value.

Algorithm

1

Check if the current node is NULL; if yes, return.

2

Recursively call postorder on the left child.

3

Recursively call postorder on the right child.

4

Print the data of the current node.

Code

c

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

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

void postorder(struct Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    printf("Postorder traversal: ");
    postorder(root);
    return 0;
}

Output

Postorder traversal: 2 3 1 

Dry Run

Let's trace the tree with root=1, left=2, right=3 through the postorder function.

1

Start at root

Current node is 1, call postorder on left child (2).

2

Visit left child

Current node is 2, call postorder on left child (NULL), returns immediately.

3

Visit right child of 2

Right child is NULL, returns immediately.

4

Print node 2

Print 2.

5

Back to root, visit right child

Current node is 3, call postorder on left child (NULL), returns immediately.

6

Visit right child of 3

Right child is NULL, returns immediately.

7

Print node 3

Print 3.

8

Back to root, print node 1

Print 1.

Step	Current Node	Action	Output So Far
1	1	Go left
2	2	Go left (NULL)
3	2	Go right (NULL)
4	2	Print 2	2
5	1	Go right	2
6	3	Go left (NULL)	2
7	3	Go right (NULL)	2
8	3	Print 3	2 3
9	1	Print 1	2 3 1

Why This Works

Step 1: Recursive calls

The function calls itself first on the left child, then on the right child, ensuring all descendants are visited before the current node.

Step 2: Base case

When the node is NULL, the function returns immediately, stopping further calls down that path.

Step 3: Processing node

After visiting left and right children, the current node's data is printed, following postorder rules.

Alternative Approaches

Iterative using two stacks

c

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

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

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void postorderIterative(struct Node* root) {
    if (!root) return;
    struct Node* stack1[MAX];
    struct Node* stack2[MAX];
    int top1 = -1, top2 = -1;
    stack1[++top1] = root;
    while (top1 >= 0) {
        struct Node* curr = stack1[top1--];
        stack2[++top2] = curr;
        if (curr->left) stack1[++top1] = curr->left;
        if (curr->right) stack1[++top1] = curr->right;
    }
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->data);
    }
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    printf("Postorder traversal (iterative): ");
    postorderIterative(root);
    return 0;
}

Uses extra memory for stacks but avoids recursion, useful when stack overflow is a concern.

Iterative using one stack and tracking last visited

c

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

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

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void postorderIterativeOneStack(struct Node* root) {
    struct Node* stack[100];
    int top = -1;
    struct Node* current = root;
    struct Node* lastVisited = NULL;
    while (top != -1 || current != NULL) {
        if (current != NULL) {
            stack[++top] = current;
            current = current->left;
        } else {
            struct Node* peekNode = stack[top];
            if (peekNode->right != NULL && lastVisited != peekNode->right) {
                current = peekNode->right;
            } else {
                printf("%d ", peekNode->data);
                lastVisited = stack[top--];
            }
        }
    }
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    printf("Postorder traversal (iterative one stack): ");
    postorderIterativeOneStack(root);
    return 0;
}

More complex but uses less memory than two-stack method; good for large trees.

Complexity: O(n) time, O(h) space

Time Complexity

Each node is visited exactly once, so the time complexity is O(n), where n is the number of nodes.

Space Complexity

The space depends on the recursion stack height, which is O(h), where h is the tree height; in worst case (skewed tree) it can be O(n).

Which Approach is Fastest?

Recursive and iterative methods have similar time complexity; iterative methods use extra memory but avoid recursion overhead.

Approach	Time	Space	Best For
Recursive	O(n)	O(h)	Simple code, small to medium trees
Iterative (two stacks)	O(n)	O(n)	Avoid recursion, easy to understand
Iterative (one stack)	O(n)	O(h)	Memory efficient iterative traversal