Skip to main content

108 - Convert Sorted Array to Binary Search Tree

Difficulty: Easy | Pattern: Divide and Conquer / Recursion | Company tags: Amazon, Airbnb, Microsoft

Problem Statement​

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is one in which the depth of the two subtrees of every node never differs by more than one.

Example:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
       0
      / \
    -3   9
    /   /
  -10  5

Approach: Divide and Conquer — O(n)​

Key insight: The middle element of a sorted array is the root of a height-balanced BST. Recursively apply this to left half (left subtree) and right half (right subtree).

Algorithm Flow​

def sortedArrayToBST(nums: list[int]):
    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

Optimized: Index-Based (Avoid Array Slicing)​

def sortedArrayToBST(nums: list[int]):
    def helper(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = helper(left, mid - 1)
        node.right = helper(mid + 1, right)
        return node
    
    return helper(0, len(nums) - 1)

Dry Run​

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

CallRangemidNodeLeftRight
helper(0,4)full20(-10,-3)(5,9)
helper(0,1)[-10,-3]0-10()(-3)
helper(1,1)[-3]1-3()()
helper(3,4)[5,9]35()(9)
helper(4,4)[9]49()()

Result BST (by level order): [0,-10,5,null,-3,null,9] ✓

Why Middle = Height Balanced​

Choosing the middle index ensures each subtree gets floor(n/2) or ceil(n/2) nodes — a difference of at most 1. This directly satisfies the height-balance property.

Edge Cases​

  • Empty array → return None
  • Single element → leaf node
  • Two elements → root + one child (left or right depending on which is mid)

Complexity​

  • Time: O(n) — every element becomes a node exactly once
  • Space: O(log n) — recursion depth of balanced tree

Key Terms​

TermDefinition
Height-balanced treeA tree where every node's two subtrees differ in depth by at most 1.
Binary search tree invariantFor every node, all left-subtree values are smaller and all right-subtree values are larger.
Divide and conquerSplitting a problem into independent subproblems (left/right halves) solved recursively.
Index-based recursionPassing left/right bounds instead of slicing arrays, avoiding O(n) copy overhead per call.
Recursion depthThe maximum number of nested calls, here O(log n) because the array is halved each level.

FAQ​

Q: Can this be solved without extra space (beyond the output tree)? A: The index-based version uses only O(log n) auxiliary space for the recursion stack, no extra arrays — the slicing version uses O(n log n) extra space due to repeated array copies.

Q: What if the input array is empty? A: sortedArrayToBST([]) returns None immediately, representing an empty tree — handled by the left > right (or not nums) base case.

Q: What if duplicate values are allowed in the array? A: The algorithm still works structurally, but the BST invariant (left < node <= right or similar strict rule) must be defined consistently, since standard BSTs typically assume unique keys.

Q: Is the resulting BST unique? A: No — when the subarray length is even, choosing the lower-middle vs upper-middle index produces a different but equally valid height-balanced BST.

Q: What is the time complexity trade-off vs building an unbalanced BST via sequential inserts? A: Sequential inserts of sorted data into a naive BST produce a degenerate O(n) height (essentially a linked list); this divide-and-conquer approach guarantees O(log n) height and O(n) total construction time.

Quick Revision​

  • Goal: build a height-balanced BST from a sorted array.
  • Key idea: the middle element becomes the root — it has equal (or near-equal) elements on both sides.
  • Recurse on the left half for the left subtree, right half for the right subtree.
  • Base case: empty range (left > right or empty slice) returns None.
  • Prefer index-based helper(left, right) over array slicing to avoid extra copies.
  • Choosing the middle guarantees each subtree gets floor(n/2) or ceil(n/2) nodes, satisfying height-balance.
  • Time: O(n) — every element visited once.
  • Space: O(log n) recursion stack (index-based) or O(n log n) (slicing version).
  • Reverse-engineer: an in-order traversal of the result always reproduces the original sorted array.