DSA AnimatorDSA animations
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.

How to solve Convert Sorted Array to Binary Search Tree

LeetCode 108 · Easy · Tree · Pattern: Divide and Conquer

Why the obvious approach is slow

Inserting the values one by one, in sorted order, makes a chain going to the right. That is a valid search tree, but it is completely unbalanced.

The key idea

Pick the middle element as the root. Everything to its left is smaller, so it builds the left subtree. Everything to its right is bigger, so it builds the right subtree. Because both halves have almost the same size, the tree stays balanced. Repeat the same rule on each half until a range is empty.

Remember

The middle element is the root, and each half becomes a subtree. Choosing the middle is what keeps the tree balanced.

Run the animation above on your own input, or watch the 2:06 video explanation of Convert Sorted Array to Binary Search Tree with a dry run and Java code.

More Tree problems