LeetCode 108: Convert Sorted Array to Binary Search Tree

Problem Restatement

We are given a sorted integer array nums in ascending order.

We need to convert it into a height-balanced binary search tree.

The official problem defines a height-balanced binary tree as a binary tree in which the depth difference between the two subtrees of every node is never more than 1. (leetcode.com)

The tree must also satisfy the binary search tree property:

left subtree values  < root value
right subtree values > root value

Because the array is already sorted, we need to arrange the numbers into a balanced BST structure.

Input and Output

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]:
        ...

Examples

Consider:

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

The middle value is:

0

This is a good root because it splits the array into two nearly equal halves:

[-10, -3]   0   [5, 9]

Now recursively build the left subtree from:

[-10, -3]

and the right subtree from:

[5, 9]

One valid balanced BST is:

         0
       /   \
     -10     5
        \     \
        -3     9

Another valid answer is also acceptable because the problem allows multiple balanced trees.

For:

nums = [1, 3]

One valid tree is:

    3
   /
  1

Another valid tree is:

    1
     \
      3

Both are balanced BSTs.

First Thought: Use the Middle Element as the Root

The array is already sorted.

If we always choose the smallest value as the root:

1
 \
  2
   \
    3

the tree becomes skewed.

Similarly, always choosing the largest value also creates a skewed tree.

To keep the tree balanced, we should choose the middle element as the root.

Then:

left half  -> left subtree
right half -> right subtree

This naturally creates balanced subtree sizes.

Key Insight

A sorted array already contains the correct inorder traversal of a BST.

For example:

[-10, -3, 0, 5, 9]

If we place the middle value at the root:

0

then all smaller values stay on the left and all larger values stay on the right.

This automatically satisfies the BST property.

Then we recursively repeat the same idea for the left and right halves.

This is a divide-and-conquer problem.

Algorithm

Define a recursive function:

build(left, right)

This function builds a BST from:

nums[left : right + 1]

For each recursive call:

1. If left > right, return None.
2. Compute the middle index.
3. Create a node using the middle value.
4. Recursively build the left subtree from the left half.
5. Recursively build the right subtree from the right half.
6. Return the node.

The middle index is:

mid = (left + right) // 2

The left subtree uses:

left to mid - 1

The right subtree uses:

mid + 1 to right

Correctness

The algorithm always chooses the middle value of the current subarray as the root node.

All values left of the middle index are smaller than the root because the array is sorted. All values right of the middle index are larger than the root. Therefore, the BST property holds at every node.

The recursive calls apply the same rule to the left and right halves. Thus, every subtree also satisfies the BST property.

Because the middle element splits the array into two nearly equal halves, the sizes of the left and right subtrees differ by at most one element at each step. Therefore, the resulting tree is height-balanced.

When the subarray becomes empty, the algorithm returns None, which correctly represents a missing child.

So the returned tree is both a valid binary search tree and height-balanced.

Complexity

Here, n is the number of elements in the array.

The recursion depth is logarithmic because the array is split approximately in half at every step.

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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) // 2

            root = TreeNode(nums[mid])

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)

            return root

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

Code Explanation

The helper function builds a subtree from one array range:

def build(left: int, right: int):

If the range is empty, there is no node:

if left > right:
    return None

Choose the middle index:

mid = (left + right) // 2

Create the root node using the middle value:

root = TreeNode(nums[mid])

Build the left subtree from the left half:

root.left = build(left, mid - 1)

Build the right subtree from the right half:

root.right = build(mid + 1, right)

Finally, return the constructed subtree root:

return root

The first call uses the full array:

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

Testing

To verify correctness, we can check:

1. The inorder traversal matches the original sorted array.
2. The tree is balanced.

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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) // 2

            root = TreeNode(nums[mid])

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)

            return root

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

def inorder(root):
    if root is None:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left = height(node.left)
        right = height(node.right)

        if left == -1 or right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

def run_tests():
    s = Solution()

    nums1 = [-10, -3, 0, 5, 9]
    root1 = s.sortedArrayToBST(nums1)
    assert inorder(root1) == nums1
    assert is_balanced(root1)

    nums2 = [1, 3]
    root2 = s.sortedArrayToBST(nums2)
    assert inorder(root2) == nums2
    assert is_balanced(root2)

    nums3 = [1]
    root3 = s.sortedArrayToBST(nums3)
    assert inorder(root3) == nums3
    assert is_balanced(root3)

    nums4 = [-5, -2, 0, 1, 8, 10]
    root4 = s.sortedArrayToBST(nums4)
    assert inorder(root4) == nums4
    assert is_balanced(root4)

    print("all tests passed")

run_tests()

Test meaning: