# Find postorder traversal of BST from preorder traversal  Difficulty Level Medium
Frequently asked in Amazon Fourkites PayU
Binary Search Tree Tree Traversal

## Problem Statement  The problem “Find postorder traversal of BST from preorder traversal” states that you are given preorder traversal of a binary search tree. Then using the given input find the postorder traversal.

## Pin  `preorder traversal sequence: 5 2 1 3 4 7 6 8 9`
`1 4 3 2 6 9 8 7 5`

## Approach  The given problem says that we are provided with a preorder traversal sequence of a binary search tree. Now we are required to find the postorder traversal of the tree which has the same preorder traversal as input. We are required to solve this problem efficiently.

A naive approach is to first use the preorder traversal and build the BST. Then simply do a postorder traversal over this newly constructed tree. But this approach is inefficient regarding space. Because the constructed tree is acting as an overhead.

To solve the problem efficiently, we go through the input array. The input array is our preorder traversal. So we go through the preorder traversal and find whether the current element should lie. When we start with the first element we set a range from minimum integer value to maximum integer value. Because the preorder traversal has the root before the left and right subtree. We know that if the left subtree exists then elements should lie from a minimum integer value to a value lesser than the root. Similarly for the right subtree that should lie from the value of greater root to a maximum integer value. Now if the current element does not lie in this range. Then that should lie in the other subtree(that is if it does not lie in range for left subtree than it should lie in the right subtree and vice-versa).

Find Maximum Level sum in Binary Tree

## Code  ### C++ code to find postorder traversal of BST from preorder traversal

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

void preToPost(int input[], int n, int mn, int mx, int& idx)
{
// base case
if (idx == n)
return;
// if current element does not belong to current subtree
if (input[idx] < mn || input[idx] > mx) {
return;
}

// store the value of root ro print after printing its subtrees
int root = input[idx];
idx++;

// recursively solve for left and right subtree
preToPost(input, n, mn, root, idx);
preToPost(input, n, root, mx, idx);
// print root
cout<<root<<" ";
}

int main()
{
int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
int n = (sizeof input)/(sizeof input);
int idx = 0;
preToPost(input, n, INT_MIN, INT_MAX, idx);
}
```
`1 4 3 2 6 9 8 7 5`

### Java code to find postorder traversal of BST from preorder traversal

```import java.util.*;

class Main{
static int idx = 0;
static void preToPost(int input[], int n, int mn, int mx)
{
// base case
if (idx == n)
return;
// if current element does not belong to current subtree
if (input[idx] < mn || input[idx] > mx) {
return;
}

// store the value of root ro print after printing its subtrees
int root = input[idx];
idx++;

// recursively solve for left and right subtree
preToPost(input, n, mn, root);
preToPost(input, n, root, mx);
// print root
System.out.print(root+" ");
}

public static void main(String[] args)
{
int input[] = {5, 2, 1, 3, 4, 7, 6, 8, 9};
int n = input.length;
preToPost(input, n, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
}```
`1 4 3 2 6 9 8 7 5`

## Complexity Analysis  ### Time Complexity

O(N), because we have to traverse the whole of the given array.

### Space Complexity

O(N), because of compiler stack which is being used for the recursive functions.