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, so there are no duplicates.
Think about it first
Hint 1
An inorder traversal of a BST visits values in sorted order — so `nums` is exactly the inorder sequence of the tree you must build. Which element should be the root so the two sides come out the same size?
Hint 2
Inserting the values one by one into an ordinary BST fails: sorted input builds a linked-list-shaped tree. You need to pick roots, not insert.
Hint 3
Take the middle element as the root, then recursively build the left subtree from the left half and the right subtree from the right half — halving guarantees the height balance.
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
Any correct output is accepted, so there is no exhaustive brute force to speak of. The naive version of the right idea is to pick the middle as root and recurse, copying each half with a slice. It is correct but wastes memory.
# 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
def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sortedArrayToBST(nums[:mid])
root.right = 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 fresh copies of the remaining array. With n = 10^4 it still passes, but the copying is unnecessary; passing indices removes 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 divide and conquer: split into independent halves, solve each recursively, and combine (here combining 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
def sortedArrayToBST(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]:
build(0, 4): mid = 2 → root 0.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.)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.
flowchart TD
A["0"] -->|left| B["-10"]
A -->|right| C["5"]
B -->|right| D["-3"]
C -->|right| E["9"]
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
def sortedArrayToBST(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).