Postorder Tree Traversal in Binary Tree in C
A binary tree is a hierarchical data structure in computer science. Each node in a binary tree can have at most two children: a left child and a right child. There are several ways to traverse a binary tree and in this article, we will learn about the postorder traversal of a binary tree in C.
Example
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
Postorder Traversal : 4 5 2 6 7 3 1
Postorder Tree Traversal in Binary Tree in C
The postorder traversal is a way of visiting all the nodes of a binary tree in a specific order. It involves visiting the left subtree first, followed by the right subtree, and finally the root node. Consider the below diagram to understand the workflow of postorder traversal:
Workflow of Postorder Traversal
Left–>right–>root
Algorithm for Postorder Traversal in C
Following is the algorithm for the postorder traversal of the binary tree in C:
- Start
- Traverse left subtree using recursion.
- Traverse right subtree using recursion
- Visit the root node
- Repeat steps 3-5 until root node != NULL
- Stop
C Program for Postorder Traversal in a Binary Tree
The following program demonstrates how we can implement the postorder traversal in a binary tree in C:
// C Program for Postorder Traversal in a Binary Tree
#include <stdio.h>
#include <stdlib.h>
// __________ CODE FOR BINARY TREE IMPLEMENTATION __________
// Define the structure for a binary tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node in a Binary Tree
struct Node* createNode(int data)
{
// Allocate memory for the new node
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
// Initialize node data and children pointers
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// __________ CODE FOR POSTORDER TRAVERSAL __________
// Function to perform postorder traversal
void postorderTraversal(struct Node* root)
{
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
// driver code
int main()
{
struct Node* root = NULL;
// Create the binary tree
/* 1
/ \
2 3
/ \ / \
4 5 6 7
*/
root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// Perform postorder traversal
printf("Postorder traversal of the binary tree is:\n");
postorderTraversal(root);
printf("\n");
return 0;
}
Output
Postorder traversal of the binary tree is: 4 5 2 6 7 3 1
Time Complexity: O(N), where N denotes the number of nodes in the binary tree
Auxiliary Space: O(log N),if space of recursive stack is not considered. If the tree is skew, then O(N)
Applications of Postorder Traversal
Following are some use cases for the post-order traversal of a binary tree:
- Used to evaluate postfix expression.
- Used to convert mathematical expressions like infix to postfix conversion.
- Used to delete or free the memory occupied by a binary tree.
- Used in compiler design for code generation and optimization tasks.
- Used in the construction and traversal of threaded binary trees.
Related Articles
The following are some articles about the post order traveral of a binary tree that can improve your knowledge:
Contact Us