BinarySearch 0225 List to Binary Search Tree

Problem statement

https://binarysearch.com/problems/List-to-Binary-Search-Tree/

Solution

Equal to Leetcode 0108. Convert Sorted Array to Binary Search Tree

Complexity

It is O(n) for time and O(log n) for additional space, not counting answer space.

Code

class Solution:
    def solve(self, nums):
        def helper(beg, end):
            if beg > end: return None
            mid = (beg + end + 1)//2
            root = Tree(nums[mid])
            root.left = helper(beg, mid - 1)
            root.right = helper(mid + 1, end)
            return root
        
        return helper(0, len(nums) - 1)