Leetcode 0108. Convert Sorted Array to Binary Search Tree

Problem statement

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Solution

This problem is the simple version of problem 109. Convert Sorted List to Binary Search Tree: here what is given not sorted linked list, but sorted array, so we can have access to any element of this array in O(1). So, the idea is straightforward: just divide our array into two almost equal halves on each iteration and attach recursive run for the left part as left subtree and recursive run for the right part as right subtree.

Complexity

Time complexity is O(n) time and O(log n) memory because of implicit stack of recursion.

Code

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