C++ program to convert preorder traversal to postorder traversal of BST

In this article, we will learn how to convert preorder traversal to postorder traversal of Binary Search Tree in C++.

A tree is said to be a binary search tree (BST) if it satisfies the following conditions

  • All the nodes of the left subtree values are less than the root nodes value.
  • All the nodes of the right subtree values are greater than the root nodes value.
  • The left and right subtree each must also be a binary search tree.

Example

Input: preorder[] = { 40, 30, 32, 35, 80, 90, 100}
Output: 35 32 30 100 90 80 40

Convert preorder traversal to postorder traversal of BST in C++

Method 1: Using the Recursive approach

In postorder first left subtree and then right subtree and then root node is printed. In preorder, the root node is always printed first, and then the left subtree and then the right subtree is printed. In this method, we first, store the first element of the preorder which is the root node and then we recursively call the left subtree and then the right subtree.

1. Firstly, make sure that the given tree is a Binary search tree.

2. Declare a variable value to store the 1st element of the preorder.

3. Now, recursively call the finfPostOrder with left subtree.

4. Then, recursively call the finfPostOrder with the right subtree.

5. Finally, print the value.

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

void findPostOrder(int preorder[], int n, int mini, int maxi, int& pre_index){
    if (pre_index == n)
    return;

    if (preorder[pre_index] < mini || preorder[pre_index] > maxi){
        return;
    }

    int value = preorder[pre_index];
    pre_index++;

    findPostOrder(preorder, n, mini, value, pre_index);
    findPostOrder(preorder, n, value, maxi, pre_index);

    cout<<value<<" ";
}
void postorder(int preorder[], int n){
    int pre_index = 0;
    findPostOrder(preorder, n, INT_MIN, INT_MAX, pre_index);
}
int main(){
    int preorder[] = {8, 3, 1, 6, 10};
    cout<<"The given preorder traversal is"<<endl;
    int n = sizeof(preorder)/sizeof(preorder[0]);
    for(int i=0;i<n;i++){
        cout<<preorder[i]<<" ";
    }
    cout<<endl;
    cout<<"The post-order traversal of the preorder traversal is:"<<endl;
    postorder(preorder, n);
    return 0;
}

Output

The given preorder traversal is
8 3 1 6 10
The post-order traversal of the preorder traversal is:
1 6 3 10 8

Method 2: 

In the preorder traversal of BST, the first element is always the root element of the tree. Iterate through the given preorder traversal of the Binary search tree and compare each element with the first element of the preorder array till the index where elements are less than the first element. Store the value of the index in a variable called val_index. Print elements of a pre-order array from val_index index to index 1. Print elements of a preorder array from index n to val_index index. The print first element of the preorder array.

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

void postorder(int preorder[], int n){
    int val_index = 0;
    for (int i=1;i<n;i++){
        if (preorder[0] <= preorder[i]){
            val_index = i;
            break;
        }
    }

    for(int i=val_index-1;i>0;i--){
        cout<<preorder[i]<< " ";
    }
    for (int i=n-1;i>=val_index;i--){
        cout<<preorder[i]<<" ";
    }
    cout<<preorder[0];
}
int main(){
    int preorder[] = {40, 30, 32, 35, 80, 90, 100, 120};
    cout<<"The given preorder traversal is"<<endl;
    int n = sizeof(preorder)/sizeof(preorder[0]);
    for(int i=0;i<n;i++){
        cout<<preorder[i]<<" ";
    }
    cout<<endl;
    cout<<"The post-order traversal of the preorder traversal is:"<<endl;
    postorder(preorder, n);
    return 0;
}

Output

The given preorder traversal is
40 30 32 35 80 90 100
The post-order traversal of the preorder traversal is:
35 32 30 100 90 80 40

Also, read

Leave a Reply

Your email address will not be published.