Conversion of BST(binary search tree) pre-order traversal to post-order traversal

Problem Statement: Post-order traversal to be printed from Pre-order traversal of a Binary Search Tree(BST).

Prerequisite: BST & traversal

A pre-order traversal of a BST is given.

In BST, value/data of all the children or nodes in left subtree is lesser than the parent and all in right subtree is greater.

In pre-order traversal first element is parent then followed by all children in left subtree, followed by all children in right subtree. And again those subtree will hold same format.

In postorder traversal, last element is parent, started with all the children in left subtree, followed by all the children in right subtree, followed by parent.

So, we know parent is the first element in pre-order traversal. But how can we divide rest of the elements into left and right subtree? It’s simple. Elements in the left subtree will be smaller than the parent, we can itterate or binary search for the parent element in rest of the elements. Once left and right subtree is identified, the same will be repeated for those subtrees. This will basically construct BST from pre-order traversal. Now, once structure of the BST is known then any order traversal can be printed.

The idea is to divide the pre-order traversal elements except for the first element into two sub-trees, say, the left sub-tree and right sub-tree. The first element of pre-order traversal is the root of the current tree. In post-order traversal, both the subtrees to be recursively processed before printing the parent or root.

//
// Created by mukuldeep maiti on 2-11-2020.
//
#include <bits/stdc++.h>
using namespace std;

void bst_pre_to_post(int pre[],int pre_start,int pre_end){
        if(pre_start>pre_end)return;
  		//finding position of the current root i.e. position of pre[pre_start]
        int premid=lower_bound(pre+pre_start+1,pre+pre_end,pre[pre_start])-pre;

  		//recursive call to left subtree
  		bst_pre_to_post(pre,pre_start+1,premid-1);
  		//recursive call to right subtree
        bst_pre_to_post(pre,premid,pre_end);
  		//printing root after processing subtrees
        cout<<pre[pre_start]<<" ";
}

int main() {

    int size=10;
    int pre[]={6,2,1,4,3,5,8,7,9,10};
    bst_pre_to_post(pre,0,size-1);

    return 0;
}

Output of the above program

1 3 5 4 2 7 10 9 8 6

Similarly, we can convert pre-order to In-order, post-order to pre-order, post-order to In-order deterministically. But incase of conversations from in-order to other forms will produce multiple possible answers, as there are multiple ways to choose the parent and so subtrees.

Any suggestions / feedback / queries – let me know in the comment section below. ❤️

Share on Social Media
Mukuldeep Maiti

Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown

You may also like...

Leave a Reply