PostOrder Traversal Code
LEFT NODE → RIGHT NODE → ROOT NODE
Binary tree we wi'll use ↓
- In the first step, you visit the left subtree considering it as a totally different tree. But before we start with the left subtree, we mark the presence of the right subtree and the root as following:
- Now, you go through the left subtree, and visit its left node first.
- And then proceed further with the right subtree of this new tree we considered. And since the right subtree of this tree has just a single element, you finish visiting it and then the root of the node, and return back to our original tree.
- And then, we visit the right subtree, and since it contains no left or right subtree further, we finish visiting our right subtree and then move to the root. And there we mark our completion of PostOrder travesal
And our final order of postorder traversal is : 5 → 2 → 1 → 6 → 4.
Code
- Create a void function postOrder and pass the pointer to the root node of the tree you want to traverse as the only parameter.
- Inside the function, check if the pointer is not NULL, otherwise we wouldn't do anyting.
- Not NULL also help to travese till last child.
- If it is not NULL, we would not directly print the data of the root since this time it's the last one to get visited
- So first, you simply call the same function recursively on the left subtree and then the right subtree using the left and right elements of the root struct.
- Once called, recursively. The function now considers the left subtree as an individual tre and applies postorder on it, and the same goes for the right subtree.
- After visiting them both, you just print the data element of the root node making it visited. And you are done.
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(int data){
struct node *n; // creating a node pointer
n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap
n->data = data; // Setting the data
n->left = NULL; // Setting the left and right children to NULL
n->right = NULL; // Setting the left and right children to NULL
return n; // Finally returning the created node
}
void preOrder(struct node* root){
if(root!=NULL){
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
int main(){
// Constructing the root node - Using Function (Recommended)
struct node *p = createNode(4);
struct node *p1 = createNode(1);
struct node *p2 = createNode(6);
struct node *p3 = createNode(5);
struct node *p4 = createNode(2);
// Finally The tree looks like this:
// 4
// / \
// 1 6
// / \
// 5 2
// Linking the root node with left and right children
p->left = p1;
p->right = p2;
p1->left = p3;
p1->right = p4;
preOrder(p);
printf("\n");
postOrder(p);
return 0;
}