Q:

# Given an array pre[] of N nodes representing preorder traversal of BST. The task is to print its postorder traversal

Given an array pre[] of N nodes representing preorder traversal of BST. The task is to print its postorder traversal.

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, the size of the array. The second line of each test case contains N input as pre[i].

Output:

Postorder traversal of the given preorder traversal is printed.

Examples:

```    Input:
T = 1
N = 8
pre[120 90 96 105 240 270 300 360]

Output:
105 96 90 360 300 270 240 120

Input:
T = 1
N = 5
pre[80 60 70 160 200]

Output:
70 60 200 160 80```

Pseudo Code:

```//postorder function to print data in postorder manner.
void postorder(Node* root)
{
//if root==NULL then simply return
if (root == NULL)
return;
else {
postorder(root->left); //recursively call for left child
postorder(root->right); //recursively call for right child
cout << root->data << " "; //print the current data
}
return;
}

//function to construct binary search tree
//from preorder traversal.
void insert(ll data)
{
Node* newnode = new Node(data);
//if root is NULL then create new node and assign it to root.
if (root == NULL)
{
root = newnode;
return;
}
else {
Node* temp = root;
while (1) {
//if data is smaller than root element then it must in left
//part of the BST so check for left side.
if (temp->data > data)
{
//if left child of root is NULL then simply assign new node
//to left part else left is assigned to
//left child and then we check again and again
//until we get correct structure.
if (temp->left == NULL) {
temp->left = newnode;
break;
}
else
temp = temp->left;
}
else {
//if data is greater than equal to root element then
//it must in right part of the BST so check for right side.
//if right child of root is NULL then simply assign new node
//to right part else right is assigned to
//right child and then we check again and again until
//we get correct structure.
if (temp->right == NULL) {
temp->right = newnode;
break;
}
else
temp = temp->right;
}
}
}
}

// solve function which will return the BST tree and print it
// postorder form after calling insert and postorder function.
void solve(int pre[],int n)
{
// add the elements to BST
for(int i=0;i<n;i++)
insert(pre[i]);
// print its postorder form.
postorder(root);
}
```
• Time Complexity for above approach is: O(n*n)
• Space Complexity for above approach is: O(n)

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node //Node structure
{
ll data; //data.
Node *left, *right; //left and right pointers.
Node(ll data)
{
this->data = data;
left = NULL;
right = NULL;
}
} * root;

//function to construct binary search tree
//from preorder traversal.
void insert(ll data)
{
Node* newnode = new Node(data);
//if root is NULL then create new node and assign it to root.
if (root == NULL)
{
root = newnode;
return;
}
else {
Node* temp = root;
while (1) {
//if data is smaller than root element then it must in left
//part of the BST so check for left side.
if (temp->data > data)
{
//if left child of root is NULL then simply assign new node
//to left part else left is assigned to
//left child and then we check again and again
//until we get correct structure.
if (temp->left == NULL) {
temp->left = newnode;
break;
}
else
temp = temp->left;
}
else {
//if data is greater than equal to root element then
//it must in right part of the BST so check for right side.
//if right child of root is NULL then simply assign new node
//to right part else right is assigned to
//right child and then we check again and again until
//we get correct structure.
if (temp->right == NULL) {
temp->right = newnode;
break;
}
else
temp = temp->right;
}
}
}
}

//postorder function to print data in postorder manner.
void postorder(Node* root)
{
//if root==NULL then simply return
if (root == NULL)
return;
else {
postorder(root->left); //recursively call for left child
postorder(root->right); //recursively call for right child
cout << root->data << " "; //print the current data
}
return;
}

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
ll n;
cout << "Enter number of nodes: ";
cin >> n;

ll pre[n];
cout << "Enter preorder traversal: ";
for (ll i = 0; i < n; i++)
cin >> pre[i];
for (ll i = 0; i < n; i++) {
insert(pre[i]); //add the elements to BST
}

cout << "Postorder traversal: ";
postorder(root); //print postorder traversal order.
cout << "\n";

//each time we need to reinitialise it
//to NULL for news tree.
root = NULL;
}

return 0;
}
``````

Output

```Enter number of test cases: 3
Enter number of nodes: 8
Enter preorder traversal: 120 90 96 105 240 270 300 360
Postorder traversal: 105 96 90 360 300 270 240 120
Enter number of nodes: 5
Enter preorder traversal: 80 60 70 160 200
Postorder traversal: 70 60 200 160 80
Enter number of nodes: 5
Enter preorder traversal: 40 30 25 80 100
Postorder traversal: 25 30 100 80 40 ```