Preorder to Postorder of BST
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
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:
C++ Implementation:
Output