Preorder Traversal of a BST Problem Statement

Given an array PREORDER representing the preorder traversal of a Binary Search Tree (BST) with N nodes, construct the original BST.

Each element in the given array is distinct, and a valid BST can always be constructed from the preorder traversal.

Your task is to construct the BST and return its inorder traversal.

Example:

Input:

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

Output:

5 10 13 15 20 30 35 42

Constraints:

• 1 <= T <= 100 - Number of test cases
• 1 <= N <= 5000 - Number of nodes in each BST
• 0 <= data <= 10^5 - Each BST node's value
• Time Limit: 1 sec

Note:

No need to print the results; implement the function to return the inorder traversal of the constructed BST for each test case.