Convert Sorted Array to Binary Search Tree

EasyBinary Tree · Divide & Conquer🧩 Tree DFS LeetCode #108 ↗Updated Oct 30, 2026

Problem

You get an integer array nums sorted in strictly increasing order. Build a binary search tree containing exactly these values that is height-balanced (at every node the two subtree heights differ by at most 1) and return its root. Any valid balanced BST is accepted.

Input[-10,-3,0,5,9]Output[0,-3,9,-10,null,5]

Input[1,3]Output[3,1] or [1,null,3]

1 ≤ n ≤ 10⁴ · -10⁴ ≤ nums[i] ≤ 10⁴ · nums is strictly increasing

Try it yourself

Java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The sorted array is the in-order traversal of the answer. Pick the middle element as the root: the halves on each side differ in size by at most 1, so recursing on them keeps every subtree balanced.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecursion on Copied Halves

Time O(n log n)Space O(n)

Take nums[mid] as the root, then literally cut the array into two new arrays with Arrays.copyOfRange and recurse on each. Every recursion level copies about n elements in total, and there are log n levels.

Java

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0) return null;
    int mid = nums.length / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
    root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
    return root;
}

Natural first draft, but the array copies add a log n factor and O(n) memory.

BetterIterative with an Explicit Stack

Time O(n)Space O(log n)

Avoid copies by describing each subtree as an index range [lo, hi]. A stack holds frames (node, lo, hi): pop one, give the node the value nums[mid], and push frames for the non-empty left/right ranges. The stack never holds more than about one frame per level.

Java

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0) return null;
    TreeNode root = new TreeNode();
    Deque<Frame> stack = new ArrayDeque<>();
    stack.push(new Frame(root, 0, nums.length - 1));
    while (!stack.isEmpty()) {
        Frame f = stack.pop();
        int mid = f.lo() + (f.hi() - f.lo()) / 2;
        f.node().val = nums[mid];
        if (f.lo() < mid) {
            f.node().left = new TreeNode();
            stack.push(new Frame(f.node().left, f.lo(), mid - 1));
        }
        if (mid < f.hi()) {
            f.node().right = new TreeNode();
            stack.push(new Frame(f.node().right, mid + 1, f.hi()));
        }
    }
    return root;
}
private record Frame(TreeNode node, int lo, int hi) {}

Linear and recursion-free, but needs a frame type and more bookkeeping.

OptimalDivide & Conquer on Index Range

Time O(n)Space O(log n)

Same index-range idea, but let recursion manage the frames: build(lo, hi) makes nums[mid] the root and attaches build(lo, mid-1) and build(mid+1, hi). Each element becomes exactly one node; recursion depth is the tree height, ≈ log n.

Java

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2; // left-middle; (lo+hi+1)/2 also works
    TreeNode node = new TreeNode(nums[mid]);
    node.left = build(nums, lo, mid - 1);
    node.right = build(nums, mid + 1, hi);
    return node;
}

Linear time, logarithmic stack, five lines — the expected answer.

Pro tip

The same “middle as root” trick converts a sorted linked list (LC 109) — find the middle with slow/fast pointers or simulate in-order.

At a glance

Level	Approach	Time	Space
Brute Force	Recursion on Copied Halves	`O(n log n)`	`O(n)`
Better	Iterative with an Explicit Stack	`O(n)`	`O(log n)`
Optimal	Divide & Conquer on Index Range	`O(n)`	`O(log n)`

Common pitfalls

Inserting values one by one into a plain BST — sorted input builds a skewed, unbalanced chain.
Off-by-one in ranges: use mid - 1 / mid + 1, and stop when lo > hi.
Expecting one exact output — left-middle and right-middle choices are both valid.

Interview tips

Start from the observation “in-order of a BST is sorted”.
Explain why the middle root guarantees balance (halves differ by ≤ 1).
Mention passing indices instead of slicing to avoid O(n log n) copying.

Pattern

Divide & conquer on a sorted range → build balanced structures by recursing on the middle.

My notes saved in this browser