Problem:

Given an array of integers preorder, which represents the preorder traversal of a BST (Binary Search Tree), construct the BST and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Example 1:

Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]

Solution:

A BST (Binary Search Tree) is a type of binary tree where the left subtree contains values lesser than the root node and the right subtree contains values greater than the root node. Hence, if we traverse the array from left to right, we can determine the structure of the tree.

In the given problem, we have the preorder traversal of the BST which means the first element in the array will be the root node of the BST. To construct the binary search tree, we can use recursion.

1. Create a recursive function called “bstFromPreorder” which takes the preorder array, a minimum value, and a maximum value as parameters, and returns the root node of the constructed BST.

2. If the preorder array is empty, return null.

3. Create a root node with the first element of the preorder array and remove it from the array.

4. If the preorder array is empty or the next element is greater than the current node, set the left child of the current node to null. Otherwise, call the “bstFromPreorder” function recursively with the preorder array, minimum value, and current value as parameters to set the left child of the current node.

5. If the preorder array is empty or the next element is lesser than the current node, set the right child of the current node to null. Otherwise, call the “bstFromPreorder” function recursively with the preorder array, current value, and maximum value as parameters to set the right child of the current node.

6. Return the root node of the BST.

Below is the implementation of the above approach.

class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def bstFromPreorder(preorder, mi, ma): if(not preorder or preorder[0] < mi or preorder[0] > ma): return None

root = TreeNode(preorder.pop(0))
root.left = bstFromPreorder(preorder, mi, root.val)
root.right = bstFromPreorder(preorder, root.val, ma)

return root

def constructBST(preorder): return bstFromPreorder(preorder, float('-inf'), float('inf'))

preorder = [8,5,1,7,10,12] root = constructBST(preorder)

Printing the inorder and

postorder of the constructed tree

def printInorder(root): if root: printInorder(root.left) print(root.val,end=" ") printInorder(root.right)

printInorder(root)

""" Output: 1 5 7 8 10 12 """

1