Preorder Traversal to BST Problem Statement

Given an array or list PREORDER representing the preorder traversal of a Binary Search Tree (BST) with N nodes, construct the BST which matches the given preorder traversal. All elements in the array have distinct values.

A BST is a binary tree data structure with the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both left and right subtrees must also be binary search trees.

Input:

The first line contains an integer 'T' representing the number of test cases. For each test case, the first line contains an integer 'N', indicating the number of nodes in the BST. The second line provides 'N' space-separated integers denoting the preorder traversal of the BST.

Output:

Print the inorder traversal of the constructed BST as a single space-separated string. Output for each test case should be printed on a separate line.

Example:

Input:

1
N = 8
PREORDER = [20, 10, 5, 15, 13, 35, 30, 42]

Output:

5 10 13 15 20 30 35 42

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 5000
• 0 ≤ data ≤ 105 where 'data' signifies the node data in the BST.

Note:

It is guaranteed that a BST can always be constructed from the given preorder traversal. Thus, a valid answer will always exist.