# Implement post-order traversal using C++ program

In this article, we are going to learn, how to implement post-order traversal using C++ program? This program contains different methods, algorithms and examples.
Submitted by Shubham Singh Rajawat, on July 24, 2017

In post-order traversal the left subtree is first then the right subtree and later then root i.e. in the order LRN (Left Right Node) where Node is the current node.

Here,
L(recursively traverse left subtree)
R(recursively traverse right subtree)
N(process node i.e. current root)

A post-order traversal can be done in two ways:

### 1. by recursive method

Algorithm:

```postorder(root)
a. Traverse the left subtree (inorder(root->left))
b. Traverse the right subtree (inorder(root->right))
c. visit the root
```

### 2. by non recursive method

This method is implemented by the use of stack.

```a. push root into the ‘post’ (first stack)
b. repeat while ‘post’ is not empty
1. pop the node from ‘post’ and push it to ‘pout’ (second stack)
2. push the left and right child of the node to ‘post’
c. print the elements of ‘pout’
```

## C++ code to implement post-order traversal

```#include<iostream>
#include<stack>
using namespace std;

/*structure to store a BST*/
struct node
{
int info;
node *left,*right;
};

/*Method to create a newNode if a tree does not exist*/
node *newNode(int n)
{
node *ptr=new node;
ptr->info=n;
ptr->left=ptr->right=NULL;
return ptr;
}

/*Method to insert given node in the BST */
node *insert(node* node,int info)
{
if(node==NULL)
{
return newNode(info);
}
if(info < node->info)
{
node->left=insert(node->left,info);
}
else
{
node->right=insert(node->right,info);
}
return node;
}

/*Method to print postorder traversal of a BST*/
void postorder(node *root)
{
stack<node*> post;
post.push(root);

stack<int> pout;
while(!post.empty())
{
node *curr=post.top();
post.pop();
pout.push(curr->info);

if(curr->left)
{
post.push(curr->left);
}
if(curr->right)
{
post.push(curr->right);
}
}
cout<<"PostOrder traversal :";
while(!pout.empty())
{
cout<<pout.top()<<" ";
pout.pop();
}
}

//Main program
int main()
{
node* root=newNode(60);

insert(root,50);
insert(root,70);
insert(root,40);
insert(root,30);
insert(root,80);
insert(root,75);
insert(root,65);
insert(root,45);
insert(root,55);
insert(root,90);
insert(root,67);

/*Call/invoke statement for postorder method*/
postorder(root);

cout<<endl;

return 0;
}
```

Output

`PostOrder traversal :30 45 40 55 50 67 65 90 80 75 70 60`

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates