Postorder Traversal of Binary Tree

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

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

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function for Postorder traversal
void postorderTraversal(struct Node* root) {
    if (root == NULL)
        return;
    
    // First traverse the left subtree
    postorderTraversal(root->left);
    // Then traverse the right subtree
    postorderTraversal(root->right);
    // Finally, visit the root node
    printf("%d ", root->data);
}

// Main function
int main() {
    // Create the root node and other nodes
    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 of the binary tree is: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

Explanation of the Code

1. Structure Definition (struct Node):
   • A Node structure is defined to represent each node in the binary tree. Each node contains:
     • data (integer value stored in the node)
     • left (pointer to the left child)
     • right (pointer to the right child)
2. createNode Function:
   • This function takes an integer data as input, allocates memory for a new node, sets its data, and initializes its left and right pointers to NULL. It returns a pointer to the new node.
3. postorderTraversal Function:
   • This function performs the postorder traversal of the binary tree:
     • It first recursively calls itself on the left subtree.
     • Then, it recursively calls itself on the right subtree.
     • Finally, it prints the data of the root node.
   • If the root is NULL, the function simply returns, which serves as the base condition for recursion.
4. main Function:
   • Creates the binary tree by calling createNode for each node.
   • The structure of the tree matches the example given above.
   • Calls postorderTraversal on the root and prints the result.

Output of the Program

When the above program is executed, the output will be:

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

This output matches the expected order of visiting nodes in postorder for the given binary tree:

1. Visit the leftmost leaf nodes (4).
2. Visit the right leaf node of the left subtree (5).
3. Visit the root of the left subtree (2).
4. Visit the right subtree (3).
5. Finally, visit the root node (1).

Thus, the program accurately implements postorder traversal for a binary tree.