Convert Sorted Array to BST

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

Question#

Given a sorted array, convert it into a height-balanced binary search tree. A height-balanced binary tree is where the depth of 2 subtrees of every node never differs by more than 1.

Implementation#

Since the BST needs to be height balanced, we cannot simply keep inserted in order. Instead, we find the middle of the array and make it the root of the BST. We recursively do this to create the left child from the start to the mid of the array and the right child from the subarray between mid to the end of the array.

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def bst(start, end):
if(start >= end):
return None
mid = (start + end) // 2
node = TreeNode(nums[mid])
node.left = bst(start, mid)
node.right = bst(mid + 1, end)
return node
return bst(0, len(nums))