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

Problem statement:

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:

#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 





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





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


© https://www.includehelp.com some rights reserved.