Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Postorder Tree Traversal in Binary Tree in C

Postorder
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.

Postorder tree Traversal in Binary Tree in C

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
Postorder Tree Traversals in BST