Problem 17.6 · Binary Search TreesEasy

Convert Sorted Array to BST

What it teaches: Building a balanced tree: the middle element is the root, and each half becomes a subtree.

Practise it on judges as “Convert Sorted Array to Binary Search Tree”.

The problem

Given a sorted array of distinct integers, build a height-balanced BST. To make the answer unique, always choose the left-middle element (lo + hi) / 2 as the root of each range.

Example 1

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

Constraints

1 ≤ n ≤ 10⁴
Sorted, distinct

Pattern clues in the wording

→ Sorted input → balanced tree

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [-10,-3,0,5,9]	[0,-10,5,null,-3,null,9]
2	nums = [1,3]	[1,null,3]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Divide at the middle · O(n)

Divide at the middle

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

build(lo, hi): if lo > hi return null; mid = (lo + hi) / 2; node with nums[mid], left = build(lo, mid − 1), right = build(mid + 1, hi).

Approach 1

class Solution {
    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) >>> 1;
        return new TreeNode(nums[mid], build(nums, lo, mid - 1), build(nums, mid + 1, hi));
    }
}

Verdict: Each element becomes one node.

Before you submit

Edge cases and common mistakes

Test these inputs

One element
Two elements

Mistakes people make

Inserting elements one by one in sorted order (builds a list, not a balanced tree).

Interview

Follow-up questions

What about a sorted linked list?

Command Palette

The problem

Approaches

Divide at the middle

Edge cases and common mistakes

Follow-up questions