Convert Sorted Array to Binary Search Tree

Problem Summary

• Given a sorted array, create a height-balanced Binary Search Tree
• The height of the tree shouldn't differ more than 1

Main Concepts Used

• Binary Search Tree
• Trees

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each node
• Space: $O(n)$ → Reason: Storing each node

Code

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def helper(start, end):
            if end < start:
                return None
            middle = (start + end) // 2
            root = TreeNode(nums[middle])
            root.left = helper(start, middle - 1)
            root.right = helper(middle + 1, end)
            return root

        return helper(0, len(nums) - 1)

Common Mistakes / Things I Got Stuck On

• Was trying to create root, left and right child outside of helper for the first layer
• helper() was already handling it