Post-order traversal in a binary tree

We all know that postorder is a form of tree traversal to visit the tree's nodes, and it helps us reach out to the tree's nodes. Postorder means visiting the lft and rt subtree recursively in a traversal operation. The postorder traversal means visiting the nodes of the trees, which implies the lft subtree firstly and then the rt subtree in the postman-order and then reaching the root node. In simple words, it follows the lft-rt-root mechanism. This type of traversal helps us get the other expression of the tree.

Algorithm

In this section, we will see the steps and understand the working of postorder traversal.

1. Step 1: Repeat Steps 2 to 4 while TREE != NILL  
2. Step 2: POSTORDER(TREE -> LFT)  
3. Step 3: POSTORDER(TREE -> RT)  
4. Step 4: Write TREE -> RECORD  
5. [END OF LOOP]  
6. Step 5: END  

Implementation

In this article section, we will see the implementation of the postorder traversal operation in the Binary tree and understand its working.

Example1)

#include <iostream>
using namespace std;


/* Given there is a B tree that has info, a ptr to the left node and ptr to the right node*/
struct Node {
	int record;
	struct Node *lft, *rt;
};


//Utility function to create a new tree node
Node* newNod(int record)
{
	Node* temp = new Nod;
	temp->record = record;
	temp->lft = temp->rt = NILL;
	return temp;
}


/* In a binary tree, we have to print all the nodes that were present in the binary tree. */
void printPO(struct Node* node)
{
	if (node == NILL)
		return;


	// first recursion found on the left sub-tree
	printPO(node->lft);


	// then recursion found on the left sub-tree
	printPO(node->rt);


	//Countering the nodes present in the tree now
	cout << node->record << " ";
}


/* In a binary tree, we have to print all the nodes that were present in the binary tree. */
void printIO(struct Node* nod)
{
	if (node == NILL)
		return;


	// first recursion found on the left sub-tree


	printIO(node->lft);
/* In a binary tree, we have to print all the nodes that were present in the binary tree. */
	cout << node->record << " ";


	// then recursion found on the rigth sub-tree
	printIO(node->rt);
}


/* In a binary tree we have to print all the nodes that were present in the binary tree. */
void printPO(struct Node* nod)
{
	if (node == NILL)
		return;


	/* first print record of node */
	cout << node->record << " ";


	/* then recur on lft subtree */
	printPO(node->lft);


	/* now recur on rt subtree */
	printPO(node->rt);
}


/* Driver program to test above functions*/
int main()
{
	struct Node* root = newNod(1);
	root->lft = newNod(2);
	root->rt = newNod(3);
	root->lft->lft = newNod(4);
	root->lft->rt = newNod(5);


	cout << "\nPreorder traversal of binary tree is \n";
	printPO(root);


	cout << "\nInorder traversal of binary tree is \n";
	printIO(root);


	cout << "\nPostorder traversal of binary tree is \n";
	printPO(root);


	return 0;
}

Output:

Example2)

#include <stdio.h>  
#include <stdlib.h>  
  
struct node {  
s  
    struct node* lft;  
    struct node* rt;  
};  
  
/*Constructing a new node*/  
struct node* createNode(int record)  
{  
    struct node* Node = (struct node*)malloc(sizeof(struct node));  
    Node->elem = record;  
    Node->lft = NILL;  
    Node->rt = NILL;  
  
    return (Node);  
}  
  
  
/*Visiting the nodes of the binary tree in the postorder form*/  
void traversePO(struct node* root)  
{  
    if (root == NILL)  
        return;  
    traversePO(root->lft);  
    traversePO(root->rt);  
    printf(" %d ", root->elem);  
}  
  
int main()  
{  
    struct node* root = createNode(40);  
    root->lft = createNode(30);  
    root->rt = createNode(50);  
    root->lft->lft = createNode(25);  
    root->lft->rt = createNode(35);  
    root->lft->lft->lft = createNode(15);  
    root->lft->lft->rt = createNode(28);  
    root->rt->lft = createNode(45);  
    root->rt->rt = createNode(60);  
    root->rt->rt->lft = createNode(55);  
    root->rt->rt->rt = createNode(70);  
      
    printf("\n The Postorder traversal of given binary tree is -\n");  
    traversePO(root);  
    return 0;  
}  

Output:

Example3)

#include <iostream>  
  
using namespace std;  
  
struct node {  
    int elem;  
    struct node* lft;  
    struct node* rt;  
};  
  
/*Constructing a new node*/  
struct node* createNode(int record)  
{  
    struct node* Node = (struct node*)malloc(sizeof(struct node));  
    Node->elem = record;  
    Node->lft = NILL;  
    Node->rt = NILL;  
  
    return (Node);  
}  
  
  
/*Visiting the nodes of the binary tree in the postorder form*/  
void traversePO(struct node* root)  
{  
    if (root == NILL)  
        return;  
    traversePO(root->lft);  
    traversePO(root->rt);  
    cout<<" "<<root->elem<<" ";  
}  
  
int main()  
{  
    struct node* root = createNode(38);  
    root->lft = createNode(28);  
    root->rt = createNode(48);  
    root->lft->lft = createNode(23);  
    root->lft->rt = createNode(33);  
    root->lft->lft->lft = createNode(13);  
    root->lft->lft->rt = createNode(26);  
    root->rt->lft = createNode(43);  
    root->rt->rt = createNode(58);  
    root->rt->rt->lft = createNode(53);  
    root->rt->rt->rt = createNode(68);  
      
    cout<<"\n The Postorder traversal of given binary tree is -\n";  
    traversePO(root);  
    return 0;  
}  

Output: