LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

Description

https://leetcode.com/problems/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]

Note: 

1. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

Explanation

the first element is the root. Then all the elements smaller than the root goes to left tree. All the elements greater than the root goes to right tree.

Python 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.helper(preorder)
        
    def helper(self, preorder):
        if len(preorder) == 0:
            return None
        
        root = TreeNode(preorder[0])
        
        left_preorder = []
        right_preorder = []

        for i in range(1, len(preorder)):
            if preorder[i] < root.val:
                left_preorder.append(preorder[i])
            else:
                right_preorder.append(preorder[i])
                
        left = self.helper(left_preorder)
        right = self.helper(right_preorder)
        
        root.left = left
        root.right = right
        
        return root
        

• Time complexity: O(NlogN).
• Space complexity: O(N).