C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Postorder Traversal in Binary Tree

Concept Overview

Postorder Traversal is one of the three fundamental Depth-First Traversal (DFS) techniques.

Traversal Order:
     Left Subtree → Right Subtree → Root

 Key Idea

  1. Visit the left child recursively.
  2. Visit the right child recursively.
  3. Visit the root node last.

This traversal is particularly useful for:

  • Deleting a tree (since you visit children before the parent).
  • Evaluating postfix expressions (in expression trees).

 

C Program: Postorder Traversal in Binary Tree

Method 1: Recursive Postorder Traversal (Simplest Form)

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for a binary tree node


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Function to create a new node


struct Node* createNode(int value) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    if (newNode == NULL) {


        printf("Memory allocation failed!\n");


        exit(1);


    }


    newNode->data = value;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Recursive Postorder Traversal (Left -> Right -> Root)


void postorderTraversal(struct Node* root) {


    if (root == NULL)


        return;


 


    postorderTraversal(root->left);   // Visit left subtree


    postorderTraversal(root->right);  // Visit right subtree


    printf("%d ", root->data);        // Visit root


}


 


int main() {


    /*


              1


             / \


            2   3


           / \


          4   5


    */


    struct Node* root = createNode(1);


    root->left = createNode(2);


    root->right = createNode(3);


    root->left->left = createNode(4);


    root->left->right = createNode(5);


 


    printf("Postorder Traversal (Recursive): ");


    postorderTraversal(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Postorder Traversal (Recursive): 4 5 2 3 1

Step-by-Step Explanation

For the tree:

       1

      / \

     2   3

    / \

   4   5

Postorder Sequence (Left → Right → Root):
4 → 5 → 2 → 3 → 1

Output → 4 5 2 3 1

 

C Program: Postorder Traversal in Binary Tree

Method 2: Iterative Postorder Traversal (Using Two Stacks)

Recursive methods are elegant but not always memory-efficient.
Let’s implement iterative postorder traversal using two stacks for better control.

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for binary tree node


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Stack structure


struct Stack {


    int top;


    int capacity;


    struct Node** array;


};


 


// Function to create a new tree node


struct Node* createNode(int data) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->data = data;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Stack utility functions


struct Stack* createStack(int capacity) {


    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));


    stack->top = -1;


    stack->capacity = capacity;


    stack->array = (struct Node**)malloc(stack->capacity * sizeof(struct Node*));


    return stack;


}


 


int isEmpty(struct Stack* stack) {


    return stack->top == -1;


}


 


void push(struct Stack* stack, struct Node* node) {


    stack->array[++stack->top] = node;


}


 


struct Node* pop(struct Stack* stack) {


    if (isEmpty(stack))


        return NULL;


    return stack->array[stack->top--];


}


 


// Iterative Postorder Traversal using two stacks


void postorderTraversal(struct Node* root) {


    if (root == NULL)


        return;


 


    struct Stack* stack1 = createStack(100);


    struct Stack* stack2 = createStack(100);


 


    push(stack1, root);


 


    while (!isEmpty(stack1)) {


        struct Node* node = pop(stack1);


        push(stack2, node);


 


        if (node->left)


            push(stack1, node->left);


        if (node->right)


            push(stack1, node->right);


    }


 


    printf("Postorder Traversal (Iterative): ");


    while (!isEmpty(stack2)) {


        struct Node* node = pop(stack2);


        printf("%d ", node->data);


    }


    printf("\n");


}


 


// Main Function


int main() {


    /*


              1


             / \


            2   3


           / \


          4   5


    */


    struct Node* root = createNode(1);


    root->left = createNode(2);


    root->right = createNode(3);


    root->left->left = createNode(4);


    root->left->right = createNode(5);


 


    postorderTraversal(root);


 


    return 0;


}

Output

 
OUTPUT :
Postorder Traversal (Iterative): 4 5 2 3 1

How the Two-Stack Method Works

Step

Stack 1 (Processing)

Stack 2 (Reverse Order)

Output

1

[1]

[]

—

2

[2,3]

[1]

—

3

[4,5,3]

[1,2]

—

4

[4,5]

[1,2,3]

—

5

[4]

[1,2,3,5]

—

6

[]

[1,2,3,5,4]

—

7

—

—

4 5 2 3 1

Final Output: 4 5 2 3 1

 

Previous
Next