pylist

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.)

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

Example 1:

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

Constraints:

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        return self.dc(preorder)
        
    def dc(self, pre):
        # return condition
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        
        # main logic
        node = TreeNode(pre[0])
        pre_l, pre_r = self.bisec(pre[0], pre[1:])
        node.left = self.dc(pre_l)
        node.right = self.dc(pre_r)
        return node
        
    def bisec(self, x, nums):
        if nums[-1] < x:
            return nums, []
        if nums[0] > x:
            return [], nums
        
        # if reach here, len(nums) must be at least 2
        low = 0
        up = len(nums) - 1
        while up - low > 1:
            mid = low + (up - low) // 2
            if nums[mid] < x:
                low = mid
            if nums[mid] > x:
                up = mid
        
        ind = up # index of the start of the 2nd half
        return nums[:ind], nums[ind:]