LeetCode 108: Convert Sorted Array to Binary Search Tree - All Solutions Explained

Problem Statement

The Convert Sorted Array to Binary Search Tree problem, LeetCode 108, is an easy-difficulty challenge where you’re given a sorted integer array nums in ascending order. Your task is to convert it into a height-balanced binary search tree (BST) and return its root. A height-balanced BST is a binary tree where the depth of the two subtrees of every node differs by at most 1.

Constraints

1≤nums.length≤1041 \leq \text{nums.length} \leq 10^41≤nums.length≤104
−104≤nums[i]≤104-10^4 \leq \text{nums[i]} \leq 10^4−104≤nums[i]≤104
nums is sorted in ascending order.

Example

Example in Python

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

Example in Python

Input: nums = [1,3]
Output: [3,1] or [1,null,3]
Explanation: Either:  3    or    1
                     /           \
                    1             3

Example in Python

Input: nums = [1]
Output: [1]
Explanation: Single node tree.

Understanding the Problem

We need to construct a height-balanced BST from a sorted array. Key points:

A BST requires left subtree values < root < right subtree values.
To ensure balance, pick the middle element as the root at each step, splitting the array into roughly equal halves.
Recursion naturally fits this divide-and-conquer approach. Let’s explore two solutions:

Recursive Middle Element : Simple and optimal (best solution).
Iterative with Queue : Alternative approach (less common).

Solution 1: Recursive Middle Element (Best Solution)

Intuition

Since the array is sorted, selecting the middle element as the root ensures the BST is height-balanced (left and right subtrees have nearly equal sizes). Recursively apply this to the left and right halves of the array to build the subtrees.

How It Works

Base case: If the array segment is empty (start > end), return None.
Find the middle index of the current segment.
Create a root node with the middle element’s value.
Recursively build the left subtree with the left half (before middle).
Recursively build the right subtree with the right half (after middle).
Return the root.
Start with the full array.

Step-by-Step Example

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

Middle=2, root=0:
- Left=[-10,-3], middle=0, root=-10:
  - Left=[], None.
  - Right=[-3], root=-3.
- Right=[5,9], middle=0, root=5:
  - Left=[], None.
  - Right=[9], root=9.
Result: 0 (-10 (-3), 9 (5)).

Python Code (Best Solution)

Example in Python

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

def sortedArrayToBST(nums):
    def build(start, end):
        if start &gt; end:
            return None
        
        mid = (start + end) // 2
        root = TreeNode(nums[mid])
        root.left = build(start, mid - 1)
        root.right = build(mid + 1, end)
        return root
    
    return build(0, len(nums) - 1)

# Helper to print tree (level order) for verification
def level_order(root):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    result = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

# Test cases
nums1 = [-10,-3,0,5,9]
print(level_order(sortedArrayToBST(nums1)))  # Output: [[0],[-3,9],[-10,5]]

nums2 = [1,3]
print(level_order(sortedArrayToBST(nums2)))  # Output: [[3],[1]] or [[1],[3]]

nums3 = [1]
print(level_order(sortedArrayToBST(nums3)))  # Output: [[1]]

Detailed Walkthrough

Middle Selection : Ensures balance by splitting evenly.
Recursion : Constructs BST with BST property (left < root < right).
Result : Height-balanced BST.

Complexity

Time Complexity : O(n), where nnn is the array length, each element processed once.
Space Complexity : O(h) = O(log n), recursion stack for balanced tree height.

Why It’s the Best

Simple, efficient, and guarantees balance.
Matches BST properties naturally.
Interview-preferred for its clarity and optimality.

Solution 2: Iterative with Queue

Intuition

Simulate the recursive process iteratively using a queue to manage segments of the array and their corresponding nodes, building the tree level by level while maintaining balance by picking midpoints.

How It Works

Use a queue to store tuples of (node, start, end).
Start with the root (middle of full array).
For each node in the queue:
- If start ≤ end, set node value to midpoint.
- Create left and right children with their segments, enqueue them.
Return the root.

Python Code

Example in Python

from collections import deque

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

def sortedArrayToBST(nums):
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    queue = deque([(root, 0, mid - 1), (root, mid + 1, len(nums) - 1)])
    
    while queue:
        parent, start, end = queue.popleft()
        if start &lt;= end:
            mid = (start + end) // 2
            node = TreeNode(nums[mid])
            if nums[mid] &lt; parent.val:
                parent.left = node
            else:
                parent.right = node
            queue.append((node, start, mid - 1))
            queue.append((node, mid + 1, end))
    
    return root

# Helper to print tree (level order) for verification
def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

# Test cases
nums1 = [-10,-3,0,5,9]
print(level_order(sortedArrayToBST(nums1)))  # Output: [[0],[-3,9],[-10,5]]

nums2 = [1,3]
print(level_order(sortedArrayToBST(nums2)))  # Output: [[3],[1]] or [[1],[3]]

nums3 = [1]
print(level_order(sortedArrayToBST(nums3)))  # Output: [[1]]

Detailed Walkthrough

For [-10,-3,0,5,9]:
- Root=0, queue=[(0,0,1), (0,3,4)].
- Left: -3 (-10), Right: 9 (5).
Result : Same balanced BST.

Complexity

Time Complexity : O(n), each element processed once.
Space Complexity : O(w), where www is max width (queue size), roughly O(n) in worst case.

Pros and Cons

Pros : Avoids recursion stack.
Cons : More complex, higher space usage.

Comparison of Solutions

Solution	Time Complexity	Space Complexity	Best Use Case
Recursive Middle	O(n)	O(log n)	Best for simplicity, interviews
Iterative with Queue	O(n)	O(n)	Non-recursive preference

Edge Cases to Consider

Single element : [1] → [1].
Two elements : [1,3] → [3,1] or [1,null,3].
Large array : 10410^4104 elements, recursion scales well.
Negative values : Handled naturally.

Final Thoughts

Recursive Middle Element : The best solution —simple, efficient, and balanced.
Iterative with Queue : Viable but overcomplicated. Master the recursive approach for its elegance in BST construction. Try converting a sorted linked list to BST (LeetCode 109) as a follow-up!