{"id":598,"date":"2024-10-19T13:50:59","date_gmt":"2024-10-19T08:20:59","guid":{"rendered":"https:\/\/codexplained.in\/?p=598"},"modified":"2025-11-24T15:34:57","modified_gmt":"2025-11-24T10:04:57","slug":"postorder-traversal-of-binary-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=598","title":{"rendered":"Postorder Traversal of Binary Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define the structure for a node of the binary tree\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = NULL;\n    newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function for Postorder traversal\nvoid postorderTraversal(struct Node* root) {\n    if (root == NULL)\n        return;\n    \n    \/\/ First traverse the left subtree\n    postorderTraversal(root->left);\n    \/\/ Then traverse the right subtree\n    postorderTraversal(root->right);\n    \/\/ Finally, visit the root node\n    printf("%d ", root->data);\n}\n\n\/\/ Main function\nint main() {\n    \/\/ Create the root node and other nodes\n    struct Node* root = createNode(1);\n    root->left = createNode(2);\n    root->right = createNode(3);\n    root->left->left = createNode(4);\n    root->left->right = createNode(5);\n\n    printf("Postorder traversal of the binary tree is: ");\n    postorderTraversal(root);\n    printf("\\n");\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Code<\/h2>\n\n\n\n
    \n
  1. Structure Definition (struct Node<\/code>)<\/strong>:\n
      \n
    • A Node<\/code> structure is defined to represent each node in the binary tree. Each node contains:\n
        \n
      • data<\/code> (integer value stored in the node)<\/li>\n\n\n\n
      • left<\/code> (pointer to the left child)<\/li>\n\n\n\n
      • right<\/code> (pointer to the right child)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • createNode<\/code> Function<\/strong>:\n
          \n
        • This function takes an integer data<\/code> as input, allocates memory for a new node, sets its data, and initializes its left and right pointers to NULL<\/code>. It returns a pointer to the new node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • postorderTraversal<\/code> Function<\/strong>:\n
            \n
          • This function performs the postorder traversal of the binary tree:\n
              \n
            • It first recursively calls itself on the left<\/code> subtree.<\/li>\n\n\n\n
            • Then, it recursively calls itself on the right<\/code> subtree.<\/li>\n\n\n\n
            • Finally, it prints the data<\/code> of the root<\/code> node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • If the root<\/code> is NULL<\/code>, the function simply returns, which serves as the base condition for recursion.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • main<\/code> Function<\/strong>:\n
                \n
              • Creates the binary tree by calling createNode<\/code> for each node.<\/li>\n\n\n\n
              • The structure of the tree matches the example given above.<\/li>\n\n\n\n
              • Calls postorderTraversal<\/code> on the root<\/code> and prints the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Output of the Program<\/h2>\n\n\n\n
                When the above program is executed, the output will be:<\/p>\n\n\n\n
                Postorder traversal of the binary tree is: 4 5 2 3 1\n<\/code><\/pre>\n\n\n\n
                This output matches the expected order of visiting nodes in postorder for the given binary tree:<\/p>\n\n\n\n
                  \n
                1. Visit the leftmost leaf nodes (4).<\/li>\n\n\n\n
                2. Visit the right leaf node of the left subtree (5).<\/li>\n\n\n\n
                3. Visit the root of the left subtree (2).<\/li>\n\n\n\n
                4. Visit the right subtree (3).<\/li>\n\n\n\n
                5. Finally, visit the root node (1).<\/li>\n<\/ol>\n\n\n\n
                  Thus, the program accurately implements postorder traversal for a binary tree.<\/p>\n