Convert Sorted Array to Binary Search Tree

Ishaan S Published 24 Oct, 2026

You are given a list nums of distinct integers sorted in strictly increasing order. Build a height-balanced binary search tree containing every value, and return its root. Height-balanced means that at every node, the heights of the two subtrees differ by at most one.

Many trees satisfy that, so to make the answer unique use this rule: for any range of the list, the root is the element at index (lo + hi) // 2, where lo and hi are the first and last indices of the range. When the range has an even number of elements, that is the left of the two middle elements. Apply the same rule recursively to the parts left and right of the chosen root.

The returned tree is shown in level order with null for missing children.

Example 1

Input: nums = [-7,-2,0,4,11] Output: [0,-7,4,null,-2,null,11] Why: The middle element 0 becomes the root. The left part [-7, -2] picks -7 (left middle) with -2 as its right child; the right part [4, 11] picks 4 with 11 as its right child.

Example 2

Input: nums = [2,6] Output: [2,null,6] Why: Two elements: the left one, 2, is the root and 6 becomes its right child.

Example 3

Input: nums = [5] Output: [5] Why: One element forms a single-node tree.

Constraints

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in strictly increasing order.

Pattern Path · Binary Search Trees · problem 98 of 169

In a BST, everything left of the root is smaller and everything right is larger. In a sorted list, which element splits it into a "smaller" part and a "larger" part of nearly equal size?

The middle element. If it is the root, the left half becomes the left subtree and the right half the right subtree.

Recurse on index ranges [lo, mid - 1] and [mid + 1, hi] instead of slicing, and return None when lo > hi.

Target: O(n) time, O(log n) recursion depth (O(n) for the output tree) extra space.

Start simple

Insert the values one by one into an ordinary BST and then rebalance it (e.g. with rotations); inserting sorted values without care builds a chain of height n with O(n²) total work.

The key idea

An in-order traversal of a BST visits its values in sorted order, so the sorted list is the in-order traversal of the tree we want. The only freedom is which element becomes each root.

Pick the middle element of the range as the root. Every element to its left is smaller, so it forms the left subtree; every element to its right forms the right subtree. Because the two parts differ in size by at most one, recursively building each part the same way keeps every subtree balanced: by induction, subtrees with sizes differing by at most one have heights differing by at most one.

Pass index bounds lo and hi rather than slicing the list, so each call does O(1) work outside the recursion. Every element becomes exactly one node, giving linear time, and the recursion depth is the tree height, about log₂ n.

Using (lo + hi) // 2 consistently picks the left middle on even-sized ranges, which makes the output match the required shape.

Complexity

Time: O(n)
Space: O(log n) recursion depth (O(n) for the output tree)

Python

class Solution:
    def sortedArrayToBST(self, nums):
        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2  # left middle on even-sized ranges
            node = TreeNode(nums[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node

        return build(0, len(nums) - 1)

JavaScript

var sortedArrayToBST = function(nums) {
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const mid = Math.floor((lo + hi) / 2); // left middle on even-sized ranges
    const node = new TreeNode(nums[mid]);
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  };
  return build(0, nums.length - 1);
};

What the interviewer is checking

It checks that you connect sorted order with in-order traversal, and that you can write a clean divide-and-conquer recursion on index ranges with correct base cases.

Mistakes to avoid

Choosing the right middle on even-length ranges, which builds a valid but different tree than the one required here.
Slicing the list at every level, which adds O(n log n) copying.
Off-by-one errors in the recursive bounds, duplicating or skipping the middle element.

Follow-ups to expect

What if the input is a sorted linked list? (Fast/slow middle, or in-order build.)
Can you build it iteratively? (Stack of index ranges.)
How would you rebalance an existing unbalanced BST? (In-order to list, then this.)

In real software

Bulk-loading a database index or building a balanced search tree from sorted data uses this middle-as-root construction instead of inserting items one at a time.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

public class Main {
    // Prints a tree in level order, with null for missing children.
    static List<Integer> levelOrder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            out.add(n == null ? null : n.val);
            if (n != null) { q.add(n.left); q.add(n.right); }
        }
        while (!out.isEmpty() && out.get(out.size() - 1) == null) out.remove(out.size() - 1);
        return out;
    }

public static void main(String[] args) {
        TreeNode root = new Solution().sortedArrayToBST(new int[]{-7, -2, 0, 4, 11});
        System.out.println(levelOrder(root)); // [0, -7, 4, null, -2, null, 11]
    }
}

Topics #098 #t-bst Array Binary Search Tree Divide and Conquer Easy Practice