Problem statement

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

Solution

We can do in simple way: find index for left part, and for right part and do recursion with time complexity O(n^2) for skewed trees and average O(n log n). There is smarter solution with O(n) time complexity, where we give the function a bound (or two bounds - up and down) the maximum number it will handle. The left recursion will take the elements smaller than node.val The right recursion will take the remaining elements smaller than bound. See also similar idea in problem 0109 Convert Sorted List to Binary Search Tree.

Complexity

It is O(n) for time and space.

Code 1

class Solution:
    def bstFromPreorder(self, preorder):
        def helper(down, up):
            if self.idx >= len(preorder): return None
            if not down <= preorder[self.idx] <= up: return None
            root = TreeNode(preorder[self.idx])
            self.idx += 1
            root.left = helper(down, root.val)
            root.right = helper(root.val, up)
            return root
        
        self.idx = 0
        return helper(-float("inf"), float("inf"))

Code 2

There is an alternative way to write it, without using global variable.

class Solution:
    def bstFromPreorder(self, preorder):
        def helper(down, up, idx):
            if idx >= len(preorder): return (idx, None)
            if not down <= preorder[idx] <= up: return (idx, None)
            root = TreeNode(preorder[idx])
            idx, root.left = helper(down, root.val, idx + 1)
            idx, root.right = helper(root.val, up, idx)
            return idx, root
        
        return helper(-float("inf"), float("inf"), 0)[1]