# 1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

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

# Solution

Approach 1: recursive, upper and lower bounds.

Approach 2: recursive, binary search for boundaries.

Approach 3: iterative, using a stack.

# Code (Python)

Approach 1:

    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        # idea: give lower and upper bounds to subtrees, O(N)
        return self._construct(preorder, -float('inf'), float('inf'))
    
    def _construct(self, preorder, lower_bound, upper_bound):
        if not preorder or preorder[0] >= upper_bound or preorder[0] <= lower_bound:
            return None
        root = TreeNode(preorder.pop(0))
        root.left = self._construct(preorder, lower_bound, root.val)
        root.right = self._construct(preorder, root.val, upper_bound)
        return root

Approach 2:

    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        # idea: search for boundaries, O(NlogN)
        return self._cons_bst(preorder, 0, len(preorder))
    
    def _cons_bst(self, nums, start, end):
        if start == end:
            return None
        
        root = TreeNode(nums[start])
        index = bisect.bisect_left(nums, root.val, start + 1, end)
        root.left = self._cons_bst(nums, start + 1, index)
        root.right = self._cons_bst(nums, index, end)
        return root

Approach 3:

    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        # idea: iterative. Use a stack to store nodes just like if we're doing trees to array.
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        stack = [root]
        for num in preorder[1:]:
            if num < stack[-1].val:
                stack[-1].left = TreeNode(num)
                stack.append(stack[-1].left)
            else:
                while stack and stack[-1].val < num:
                    node = stack.pop()
                node.right = TreeNode(num)
                stack.append(node.right)
        return root

# Code (C++)

Approach 1:

Approach 2: