1

BST from Preorder

Difficulty: MEDIUM
Contributed By

Problem Statement

You are given a preorder traversal of a binary search tree, your task is to find the tree from the given preorder traversal.

For example:
You are given preOrder = [10, 5, 1, 7, 40, 50], the binary search tree from the given preorder traversal is 

sample1

Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of the preorder array.

The second line of each test case contains ‘N’ space-separated integers representing the preorder traversal of the tree.
Output Format:
For each test, ‘N’ space-separated integers will be printed representing the inorder traversal of the tree.

Print a separate line for each test case.
Constraints:
 1 <= T <= 10
 1 <= N <= 10^6
 1 <= preOrder[i] <= 10^9

 It is guaranteed that the sum of ‘N’ over all test cases does not exceed 10^6.

Time Limit: 1 sec.
Note:
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1
2
6
10 5 1 7 40 50
6
8 5 1 7 10 12
Sample Output 1:
1 5 7 10 40 50
1 5 7 8 10 12
Explanation:
For the first test case,  preOrder = [10, 5, 1, 7, 40, 50], the binary search tree from the given preorder traversal is 

sample1

Hence the answer is [1, 5, 7, 10, 40, 50].

For the second test case,  preOrder = [8, 5, 1, 7, 10, 12], the binary search tree from the given preorder traversal is 

sample2

Hence the answer is [1, 5, 7, 10, 40, 50].
Sample Input 2:
2
3
2 1 3
3
1 3 2
Sample Output 2:
1 2 3
1 2 3
Reset Code
Full screen
copy-code
Console