C Program to Traverse a Binary Tree Using Postorder Traversal

Introduction

Postorder traversal is a type of depth-first traversal method for binary trees. In postorder traversal, the nodes are recursively visited in the following order: left subtree, right subtree, root node. This traversal method is particularly useful when you need to delete or process all the children of a node before the node itself, such as when deleting a tree from the leaves up to the root.

Example:

• Tree Structure:

       1
      / \
     2   3
    / \
   4   5
  

• Postorder Traversal Output: 4 5 2 3 1

Problem Statement

Create a C program that:

• Constructs a binary tree.
• Traverses the binary tree using postorder traversal.
• Outputs the nodes in the order they are visited.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output and memory allocation functions.
2. Define the Structure for a Tree Node: Each node will contain a data value and pointers to its left and right children.
3. Implement the Postorder Traversal Function: This function will traverse the binary tree in postorder.
4. Create a Main Function: Build a sample binary tree and perform postorder traversal.

C Program to Traverse a Binary Tree Using Postorder Traversal

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

// Define the structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new tree node
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;
}

// Function to perform postorder traversal of the binary tree
void postorderTraversal(struct Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);   // Traverse the left subtree
        postorderTraversal(root->right);  // Traverse the right subtree
        printf("%d ", root->data);        // Visit the root node
    }
}

int main() {
    // Creating a sample binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Perform postorder traversal
    printf("Postorder traversal of the binary tree is: ");
    postorderTraversal(root);
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Structure for a Tree Node

• The struct Node defines a node of the binary tree, which contains an integer data and pointers to its left and right children.

Function to Create a New Tree Node

• The newNode function creates a new node with the given data, initializes its left and right pointers to NULL, and returns the pointer to the new node.

Function to Perform Postorder Traversal

• The postorderTraversal function recursively visits nodes in the order: left subtree, right subtree, root node. The function uses a simple base case: if the current node is not NULL, it proceeds with the traversal; otherwise, it returns.

Main Function

• The main function constructs a sample binary tree and calls the postorderTraversal function to print the nodes in postorder.

Output Example

Example Output:

Postorder traversal of the binary tree is: 4 5 2 3 1

Example Output (Different Tree):

If the binary tree is modified, for example:

       10
      /  \
     20   30
    / \
   40  50

The postorder traversal will be:

Postorder traversal of the binary tree is: 40 50 20 30 10

Conclusion

This C program demonstrates how to traverse a binary tree using postorder traversal. Postorder traversal is useful in scenarios where you need to process all child nodes before the parent node, such as in deletion operations. The program provides a practical example of how to implement and use postorder traversal in C programming.