Convert Sorted Array to Binary Search Tree

Question (LC.108)

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Example

Input: nums = [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5] 

      0
     / \
   -3   9
   /   /
 -10  5
 
 Another possible answer is: [0,-10,5,null,-3,null,9]
 
       0
     /   \
   -10    5
   /  \  /  \
 null -3 null 9    

Analysis

Divide and conquer the array. Be careful on the even and odd case on how to divvy up the subarray.

Code

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
    
    n = len(nums)
    
    if n == 0:
        return None
    
    return self.arrToBST(nums, 0, n-1)



def arrToBST(self, nums: List[int], start: int, end: int) -> Optional[TreeNode]:
    
    # base 
    
    if start > end:
        return None
    
    if start == end:
        return TreeNode(nums[start])
    
    
    # divide 
    
    mid = (start + end) // 2 
    
    left_tree = self.arrToBST(nums, start, mid-1)
    right_tree = self.arrToBST(nums, mid+1, end)
    
    # merge 
    return TreeNode(nums[mid], left_tree, right_tree)

O(n) time and O(n) space