C Program to Traverse a Binary Tree Using Postorder Traversal

C Program to Traverse a Binary Tree Using Postorder Traversal

By /

Postorder traversal is a method of visiting all nodes in a binary tree by first traversing the left subtree, then the right subtree, and finally the root node. This traversal is useful for deleting trees, evaluating postfix expressions, and performing bottom-up computations. Understanding postorder traversal is essential for tasks that require processing child nodes before their parent.

Understanding the Problem

The challenge in postorder traversal is ensuring that both the left and right subtrees of a node are fully processed before visiting the node itself. Recursion provides a simple and natural way to implement this traversal. Iterative approaches using two stacks or one stack with a marker are alternatives for larger trees where recursion may be limited by stack depth.

Program: Recursive Postorder Traversal of a Binary Tree

This program demonstrates postorder traversal, printing each node’s value after traversing its children. The binary tree nodes are dynamically allocated and linked, and recursion is used to traverse the tree.

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

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

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Recursive postorder traversal
void postorderTraversal(Node *root) {

    if (root != NULL) {

        postorderTraversal(root->left);
        postorderTraversal(root->right);

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

    }

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Postorder Traversal: ");
    postorderTraversal(root);

    printf("\n");

    return 0;

}

The program defines a Node structure with data, left, and right pointers. The createNode function allocates memory for each node dynamically. The postorderTraversal function recursively traverses the left and right subtrees before printing the current node’s value. This ensures that parent nodes are processed only after all their children, following the postorder sequence.

Program: Iterative Postorder Traversal of a Binary Tree

This program demonstrates how to traverse a binary tree in postorder fashion without recursion, using an explicit stack to manage nodes.

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

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

// Stack structure
typedef struct Stack {
    Node **arr;
    int top;
    int capacity;
} Stack;

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Stack functions
Stack* createStack(int capacity) {

    Stack *stack = (Stack*) malloc(sizeof(Stack));
    stack->arr = (Node**) malloc(capacity * sizeof(Node*));
    stack->top = -1;
    stack->capacity = capacity;

    return stack;

}

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

    if (stack->top < stack->capacity - 1) {
        stack->arr[++stack->top] = node;
    }

}

Node* pop(Stack *stack) {

    if (stack->top >= 0) {
        return stack->arr[stack->top--];
    }

    return NULL;

}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// Iterative postorder traversal using two stacks
void postorderIterative(Node *root) {

    if (root == NULL) return;

    Stack *stack1 = createStack(100);
    Stack *stack2 = createStack(100);
    push(stack1, root);

    while (!isEmpty(stack1)) {

        Node *node = pop(stack1);
        push(stack2, node);

        if (node->left) push(stack1, node->left);
        if (node->right) push(stack1, node->right);

    }

    while (!isEmpty(stack2)) {
        Node *node = pop(stack2);
        printf("%d ", node->data);
    }

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Iterative Postorder Traversal: ");
    postorderIterative(root);
    printf("\n");

    return 0;

}

In this program, two stacks are used to simulate the recursive postorder traversal. The first stack is used to process nodes in a modified preorder fashion, while the second stack reverses the order to produce the correct postorder sequence. This ensures that parent nodes are printed only after all children have been visited, achieving postorder traversal without recursion.

The recursive postorder traversal is simple and easy to implement, making it suitable for small to medium trees or situations where clarity is more important than efficiency. The iterative postorder traversal, which typically uses two stacks, avoids potential stack overflow and is better for very deep or large trees where memory control and stability are important. In short, recursion is handy for simplicity, while iteration is handy for robustness in large structures.

FAQs

Q1: How does postorder traversal differ from inorder and preorder?
Postorder visits left, right, root; inorder visits left, root, right; preorder visits root, left, right.

Q2: What are common applications of postorder traversal?
Postorder is used for deleting trees, evaluating postfix expressions, and performing computations that depend on child nodes first.

Q3: Can postorder traversal be done iteratively?
Yes, using two stacks or a single stack with markers, iterative postorder traversal is possible.

Q4: What is the time complexity of postorder traversal?
O(n), where n is the number of nodes, as each node is visited exactly once.

Conclusion

Postorder traversal is a fundamental technique for processing child nodes before their parent in a binary tree. It is particularly useful for deletion, postfix evaluation, and bottom-up operations. Mastery of postorder traversal enhances understanding of recursion and prepares for more advanced tree algorithms.

References & Additional Resources

A curated collection of books and online resources providing both theoretical foundations and practical examples for understanding binary trees, dynamic memory allocation, and related data structures in C.

  1. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees, dynamic memory allocation, and other fundamental data structures.
  2. Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, essential for data structure implementation.
  3. GeeksforGeeks: Binary Tree in C – Explanation of binary tree concepts, structure, and implementation in C.
  4. GeeksforGeeks: Binary Tree Traversal in C – Covers inorder, preorder, and postorder traversal techniques with examples.
  5. Programiz: Data Structures – Binary Tree – Beginner-friendly guide with examples for traversal, insertion, and deletion.
  6. Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of malloc(), calloc(), realloc(), and free() functions for memory management.

Related Posts

Scroll to Top