Postorder Tree Traversal in Binary Tree in C Direction (Inorder) Anti Clock Rule Left Right Center(LRC)

Postorder Traversal of the Tree in C

Postorder traversals is one of thmost frequently used tree traversals, in such traversal we try to print the left most root first. Let us see how post order tree traversals work –

Working of PostOrder Algorithm

• We traverse in Anti Clock wise Direction
• Rule followed is LRC(Left-Right-Center)

Which means that we try to visit the leftmost node of the tree first and then its subtree’s right node and then center/middle node and keep on doing the same iteratively. Working for the above image for Postorder traversal

We traverse the tree and try to go to the left most node

• Here, Leftmost item is 8, right item : 9, middle item : 4 (Now recursive moving in the tree)
• Print 8 9 4
• Leftmost item is 4 (However, we’ve visited it already), so now, right item is 5 then middle item : 2
• Print 5 2
• The left side of the tree is done, moving to right side of the tree
• (In right subtree) The leftmost item: NULL, and its right item is: 10, middle item: 10 (Move up the tree)
• Print 10 6
• Central item, 3, however 3 has child elements, so we try to visit its subtree’s
• Now, we come across 7, which still has a subtree so we recur down the tree
• The left node of 7 is last node in the tree and left most, its right sibling: 12, middle: 7
• Print: 11 12 7
• Now, recurring up, whole subtree (Both left & right of 3 is printed so
• Print 4

Algorithm for Postorder Traversal

Postorder(root)

• Traverse the left sub-tree, (recursively call postorder(root -> left).
• Traverse the right sub-tree, (recursively call postorder(root -> right).
• Visit and print the root node.
// PrepInsta's program for postorder traversal
#include <stdio.h>
#include <stdlib.h>

// Basic struct of Tree
struct node
{
int val;
struct node *left, *right;
};

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

// Function print the node in postorder format, when insertion is complete
void postorder(struct node* root)
{
if (root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ", root->val);
}
}

// Here we are finding where to insert the new node so BST is followed
struct node* insert(struct node* node, int val)
{
/* If the tree(subtree) is empty, return a new node by calling newNode func.*/
if (node == NULL) return newNode(val);

/* Else, we will do recursion down the tree to further subtrees */
if (val < node->val)
node->left  = insert(node->left, val);
else if (val > node->val)
node->right = insert(node->right, val);

/* (Safety) return the node's pointer which is unchanged */
return node;
}

int main()
{
/* Our BST will look like this
90
/     \
70      130
/  \    /  \
50   75  110  150 */
struct node* root = NULL;
root = insert(root, 90);
insert(root, 70);
insert(root, 50);
insert(root, 75);
insert(root, 130);
insert(root, 110);
insert(root, 150);

// Finally printing the tree using postorder
postorder(root);

return 0;
}

Output –

50 75 70 110 150 130 90 