[Leetcode]1008. Construct Binary Search Tree from Preorder Traversal

Question:
Given a preorder traversal, reconstruct the binary search tree and return the root.

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Visiualization of the output:

If we know how to traversal a tree in preorder – visit the current node and then move to the left and right children – we can reconstruct the tree following this manner. The brute force way is quite intuitive: as shown below, we can set the first element 8 as the root; all of the smaller elements starting from it will compose the left subtree and the remaining elements will compose the right subtree.

def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
    def helper(left=0,right=len(preorder)):
        if left >= right:
            return None
        root = TreeNode(preorder[left])
        if left == right-1:
            return root
        new_left = right
        for i in range(left,right):
            if preorder[i] > preorder[left]:
                new_left = i
                break
        root.left = helper(left+1,new_left)
        root.right = helper(new_left,right)
        return root
    return helper()

The time complexity for it will be O(n^2) since it needs to loop through the array to split the elements into left and right subtree.

There are some improvements that we could apply so as to reduce the time complexity to O(nlogn) or even O(n). The following solutions are from @lee215.

The first improvement is to utilize binary search when we need to find the elements that are larger than the root. With binary search we could achieve O(nlogn).

Python package bisect provides convenient API for that.
Notably, for each range [left,right), we excluded the right boundary so that we don’t have to deal with +1 or -1.

def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
    def helper(left=0,right=len(preorder)):
        if left >= right:
            return None
        root = TreeNode(preorder[left])
        i = bisect.bisect(preorder,preorder[left],left+1,right)
        root.left = helper(left+1,i)
        root.right = helper(i,right)
        return root
    return helper()

Or, we don’t have to split the array each time. We set a bound as the largest element it could handle. As shown below, bound for the node’s left subtree is the node itself, while bound for its right subtree should be the node’s parent.

def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
    def helper(arr=preorder,bound=float('inf')):
        if not arr or arr[0]>bound:
            return None
        root = TreeNode(arr.pop(0))
        root.left = helper(arr,root.val)
        root.right = helper(arr,bound)
        return root
    return helper()

The time complexity is O(n) because we visit each node once.