← Back to DSA Animator
Convert Sorted Array to BST LC #108 Easy BST · Divide & Conquer · Recursion
Problem

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

Example 1
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: Mid=0 becomes root, left=[-10,-3], right=[5,9]. Multiple valid answers exist.
Example 2
Input: nums = [1,3]
Output: [3,1] or [1,null,3]
Explanation: Either node can be the root; both are valid height-balanced BSTs.
Example 3
Input: nums = [1,2,3,4,5,6,7]
Output: [4,2,6,1,3,5,7]
Explanation: Perfectly balanced 3-level tree with root 4.
Constraints: 1 ≤ nums.length ≤ 10⁴  |  −10⁴ ≤ nums[i] ≤ 10⁴  |  nums is sorted in strictly ascending order
Try Examples
Custom:
Approach
Divide & Conquer: mid element → root, recurse halves
Pick the middle index as root to keep left/right subtrees equal in size. Recurse on lo..mid-1 (left) and mid+1..hi (right). BST property holds automatically because the array is sorted.
BST Being Built
Select an example…
Array Visualizer
Range: lo=— · mid=— · hi=—
Call Stack
Variables
lo
—
hi
—
mid
—
depth
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Base case: lo > hi → return null
2
Compute mid: mid = lo + (hi − lo) / 2
3
Create node: node = new TreeNode(nums[mid])
4
Recurse left half: node.left = build(lo, mid−1)
5
Recurse right half: node.right = build(mid+1, hi)
Time
O(n)
Space
O(log n)
Why Height-Balanced?

Choosing the midpoint as root ensures the left and right subtrees have sizes that differ by at most 1. Since the array is sorted, elements to the left of mid are all smaller (BST left subtree) and elements to the right are all larger (BST right subtree). Applying this rule recursively at every level guarantees a height-balanced BST where |height(left) − height(right)| ≤ 1 at every node.