New update is available. Click here to update.

Last Updated: 24 Nov, 2020

Moderate

```
β’ 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 the left and right subtrees must also be binary search trees.
```

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

```
From PREORDER = [20, 10, 5, 15, 13, 35, 30, 42] , the following BST can be constructed:
```

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N' denoting the number of nodes in BST.
The second line of each test case contains 'N' single space-separated integers representing the preorder traversal of BST.
```

```
Print the inorder traversal of the constructed BST where all nodes are printed in a single-space separated manner.
Output for every test case will be printed in a separate line.
Note:
You don't need to print anything. It has already been taken care of. Just implement the function.
```

```
1 <= T <= 100
1 <= N <= 5000
0 <= data <= 10^5
Where 'data' denotes data contained in the nodes of the binary search tree.
Time Limit: 1 sec
```

Approaches

We have a simple Brute Force solution for this problem. We will traverse the PREORDER array, find the left subtree and right subtree and then recursively construct the tree as follows-

- The first element of the preorder traversal corresponds to the root of BST
*.* - We will find the index βSPLITβ of the first element in the given traversal which is greater than the root node i.e PREORDER[βSPLITβ] > PREORDER['START'].
- We will split the given array to the left subarray ['START' + 1 : βSPLITβ - 1] and right subarray [βSPLITβ: βENDβ] corresponding to the left subtree and right subtree, respectively.
- We then recursively repeat the above steps for both subtrees to construct the complete tree.

The idea is based on the fact that the value of each node in a BST is greater than the value of all nodes in its left subtree and less than the value of all nodes in its right subtree.

So, instead of explicitly searching for indices that split the left and the right subtree (as in the previous approach), we will pass the information about the valid range of values for a node and its children in recursion itself.

- We will maintain βMIN_VALβ
- We will also maintain βPRE_ORDER_INDEXβto keep track of the index in the βPRE_ORDER_INDEXβ
- We initialize βCURR_VALβ to βPREORDERβ[βPRE_ORDER_INDEXβ].
- If βCURR_VALβ doesnβt fall in the range [βMIN_VALβ: βMAX_VALβ
- Else, we construct βNODEβ initialized to βCURR_VALβ and increment βPRE_ORDER_INDEXβ.

- If βCURR_VALβ doesnβt fall in the range [βMIN_VALβ: βMAX_VALβ
- We will then set the range for the left subtree ([βMIN_VALβ : βCURR_VALβ + β1β) and the right subtree (['CURR_VAL' +1 : βMAX_VALβ]) and recursively construct them.

Similar problems