Convert Sorted Array to Binary Search Tree

Intuition

Because the array is already sorted, an in-order traversal of any BST built from it must reproduce the array. To keep the tree balanced we want roughly equal numbers of elements on both sides of each root, which is exactly what choosing the middle element accomplishes. The elements to the left of the middle form the left subtree and those to the right form the right subtree, and each half is solved with the same procedure. Recursion naturally handles arbitrarily deep splitting, and the base case is an empty range that produces a null child. Since each index becomes a node exactly once, the construction is linear.

Algorithm walkthrough

1. 1Define a helper build(left, right) that constructs a BST from the inclusive index range.
2. 2If left > right the range is empty, so return null.
3. 3Compute mid = left + (right - left) / 2 to avoid overflow and pick a balanced pivot.
4. 4Create a node holding nums[mid].
5. 5Recursively build the left subtree from [left, mid - 1] and the right subtree from [mid + 1, right].
6. 6Return the node; the initial call build(0, n - 1) returns the tree root.

Implementation

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            mid = left + (right - left) // 2
            node = TreeNode(nums[mid])
            node.left = build(left, mid - 1)
            node.right = build(mid + 1, right)
            return node

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