Construct BST from Preorder Traversal

In this approach, it can be observed that the first element of the preorder array will always be the root of the BST. We can then note that all the elements after the first element, which are less than the root, will be in the left subtree of the root, and all the elements that are larger than the root will be in the right subtree of the root.

Therefore for each root, we create two arrays leftPreOrder, rightPreOrder, then divide the elements of the preOrder traversal into two arrays according to whether the elements are greater than the root element or not.

We will create recursive function util(preOrder), here preOrder is the preOrder traversal of the tree. 

Algorithm:

• In the function util(preOrder)
  • If the size of preOrder is 0 return Null
  • Set root as TreeNode(preOrder[0])
  • Set leftPreOrder as the array with all the elements of preOrder that are smaller than preOrder[0]
  • Set rightPreOrder as the array with all the elements of preOrder that are smaller than preOrder[0]
  • Set root.left as util(leftPreOrder)
  • Set root.right as util(rightPreOrder)
• Return util(preOrder)

In this approach, instead of separating the array, we will use the keep a variable preIndex, which will keep track of the current root node, in the preorder array. We will use ranges because, for any node in the right subtree,it has to be larger than the root, so for every subtree in the tree we can maintain a range, which is the largest value in the current subtree and the smallest value in the current subtree.
 

We will create a utility recursive function util(preOrder, preIndex, startRange, endRange),  where startRange and endRange is the range of values allowed in the current subtree.

Algorithm:

• In the util(preOrder, preIndex startRange, endRange)
  • If preIndex is greater than the size of preOrder array , return Null
  • Set currNode as preOrder[preIndex]
  • If currNode is greater than startRange and less than endRange
    • Set root as TreeNode(root)
    • Increase preIndex by 1
    • If preIndex is less than size of preOrder array
      • Set root.left as util(preOrder, preIndex, startRange, currNode)
    • If preIndex is less than the size of preOrder array
      • Set root.right as util(preOrder, preIndex, currNode, endRange)
    • Return the root
  • Otherwise, return Null
• Set preIndex as 0
• Return util(preOrder, preIndex,  +infinity, -infinity)