Convert Sorted Array to Binary Search Tree

Problem

You are given an integer array nums sorted in strictly increasing order. Build and return a height-balanced binary search tree containing exactly these values — height-balanced meaning at every node, the left and right subtree heights differ by at most 1.

Any valid answer is accepted; many differently-shaped balanced BSTs can hold the same values.

Examples

Example 1

Input:  nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]   (one valid answer)

         0
        / \
      -3   9
      /   /
    -10  5

0 is the middle element; everything smaller goes left, everything larger goes right, recursively.

Example 2

Input:  nums = [1,3]
Output: [3,1]  — and [1,null,3] is equally valid.

With an even count there is no unique middle; either choice yields a balanced BST.

Constraints

• 1 <= nums.length <= 10^4 — an O(n) construction is expected.
• -10^4 <= nums[i] <= 10^4, strictly increasing — no duplicates to worry about.

Think about it first

TL;DR

Divide and conquer: middle element becomes the root, recurse on each half — O(n) time, O(log n) auxiliary space with index-based recursion.

Approach 1 — Brute force: naive recursion with array slicing

There is no meaningful “try everything” brute force here (any correct output is accepted), so the ladder starts at the naive implementation of the right idea: pick the middle as root and recurse, but copy the halves with slices. Correct, just needlessly memory-hungry.

# 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

from typing import Optional, List


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

Complexity: O(n log n) time and O(n log n) total allocated space — every level of the recursion slices out fresh copies of the whole remaining array. With n = 10^4 it still passes easily, but the copying is pure waste; indices eliminate it.

Approach 2 — Divide and conquer on index bounds

The insight: the slices only ever describe a contiguous window of the original array, so pass (lo, hi) bounds instead of copies. This is textbook divide and conquer — the classical strategy of splitting a problem into independent halves, solving each recursively, and combining (here the “combine” is just wiring up child pointers). Choosing the middle guarantees the two halves differ in size by at most 1, which inductively makes every subtree height-balanced.

# 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

from typing import Optional, List


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

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

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

1. build(0, 4): mid = 2 → root 0.
2. build(0, 1): mid = 0 → node -10; its left is build(0,-1) = None, its right is build(1,1) → node -3. (This yields the mirror-image of the example tree — equally valid.)
3. build(3, 4): mid = 3 → node 5; right is build(4,4) → node 9.

Resulting tree: 0 with left -10 → (right) -3 and right 5 → (right) 9 — every node’s subtree heights differ by at most 1.

Complexity: O(n) time — each element becomes a node exactly once. O(log n) auxiliary space for the recursion stack (the depth is log n because the range halves each call); O(n) counting the output tree.

Approach 3 — Iterative with an explicit stack

The insight: the recursion carries only (node-to-fill, lo, hi) triples, so an explicit stack can simulate it — the classic recursion-to-iteration transformation, handy when the language’s call stack is a concern or the interviewer asks for “no recursion.”

# 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

from typing import Optional, List


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = (len(nums) - 1) // 2
        root = TreeNode(nums[mid])
        # each entry: (node, lo, hi) where node.val == nums[(lo+hi)//2]
        stack = [(root, 0, len(nums) - 1)]
        while stack:
            node, lo, hi = stack.pop()
            mid = (lo + hi) // 2
            if lo <= mid - 1:
                lmid = (lo + mid - 1) // 2
                node.left = TreeNode(nums[lmid])
                stack.append((node.left, lo, mid - 1))
            if mid + 1 <= hi:
                rmid = (mid + 1 + hi) // 2
                node.right = TreeNode(nums[rmid])
                stack.append((node.right, mid + 1, hi))
        return root

Walkthrough on nums = [1, 3] (example 2): mid = 0 → root 1; the stack entry (1, 0, 1) pops, left range [0,-1] is empty, right range [1,1] creates node 3 as 1’s right child. Output [1,null,3] — one of the two accepted shapes.

Complexity: O(n) time, O(log n) stack space — identical to the recursion, just explicit.

Common pitfalls

• Building by repeated BST insertion: sorted input degenerates into a height-n chain, violating the balance requirement.
• Off-by-one in the base case: recurse while lo <= hi and stop on lo > hi; stopping on lo == hi drops single-element ranges.
• Recomputing mid inconsistently (floor vs ceil) between the root pick and the recursive bounds — pick one convention and reuse it.
• Worrying that your tree doesn’t match the judge’s example output: any height-balanced BST over the values is accepted; both middle choices on even-length ranges are fine.

Pattern takeaway

A sorted array is a BST’s inorder sequence flattened — to rebuild a balanced tree, repeatedly promote the middle to root and recurse on the halves. More generally, “balanced structure from ordered data” almost always means divide and conquer on index bounds: halving the range bounds the height at O(log n) by construction, and passing indices instead of slices keeps it O(n).