Home »
Interview coding problems/challenges
Preorder to Postorder of BST
Preorder to Postorder of BST: Here, we are going to learn the solution of Preorder to Postorder of BST – The problem has been featured in interview rounds of many top tech companies such as Amazon, Linkdin etc.
Submitted by Divyansh Jaipuriyar, on May 24, 2020 [Last updated : March 20, 2023]
Problem Description
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
Solution Approach
Since we are given the preorder traversal of the tree, to construct any tree we need at least two traversal {inorder,preorder},{inorder,postorder},{inorder,levelorder} that is inorder is needed, but here only one traversal is given but one more important thing is the property of this tree, that is this tree is BST, which has its left child less than or equal to the root of the tree and right child as greater than the root element. So we will use this property and construct a BST and then we simply print the Postorder traversal of the tree.
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 of Preorder to Postorder of BST
#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