Turn a Sorted List Into a Balanced Search Tree

Easy15–20 min

Topics

Binary Search TreeBSTDivide and ConquerConstruction

Companies

AmazonMicrosoftGoogleFacebookApple

You are given an array of integers sorted in strictly increasing order. Build a height-balanced binary search tree that contains exactly these values and return its root. To make the result unique, always choose the middle element of a range as its root (when the range has an even number of elements, the left one of the two middle elements), and build the left and right subtrees from the elements before and after it.

Copying sub-arrays at every step is easy but wasteful; passing index ranges builds the same tree with no copying.

Test Case 1:

Input:nums = [3, 7, 12, 18, 25, 31]

Output:[12, 3, 25, null, 7, 18, 31]

Explanation:Six values: the left middle 12 is the root. The left part [3, 7] uses its left middle 3 as root with 7 as its right child; the right part [18, 25, 31] has root 25 with children 18 and 31.

Test Case 2:

Input:nums = [-5, 0, 5]

Output:[0, -5, 5]

Explanation:Three values form a perfect small tree around the middle one.

Test Case 3:

Input:nums = []

Output:[]

Explanation:No values, no tree.

Constraints

◆0 ≤ nums.length ≤ 100; nums is sorted in strictly increasing order; −1000 ≤ nums[i] ≤ 1000
◆Build a binary search tree that contains exactly these values and is height-balanced (at every node the two subtree heights differ by at most 1)
◆To make the answer unique: the root of any range of values is its MIDDLE element, and when the range has an even number of elements the LEFT of the two middle elements is used (index (lo + hi) / 2, rounded down)
◆Return the root of the tree (checked as a level-order list); an empty list gives the empty tree

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Copy the Left and Right Parts at Every Level

Brute

Take the middle element as the root (the left one of two for an even length), then build the left subtree from a COPY of the elements before it and the right subtree from a COPY of the elements after it, recursing on the copies. Halving at every step keeps the tree balanced and the ordering makes it a valid search tree. It is correct, but every level copies all remaining elements: O(n) work per level over log n levels, i.e. O(n log n) time (and extra memory for the copies).

TimeO(n log n)

SpaceO(n)

Java

Try it out

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

Optimal — Recurse on Index Ranges Instead of Copies

Optimal

The same divide-and-conquer, but pass the range [lo, hi] of the ORIGINAL array instead of making copies: if lo > hi the range is empty (no node); otherwise the root is nums[mid] with mid = (lo + hi) / 2, the left subtree is built from [lo, mid − 1] and the right subtree from [mid + 1, hi]. Each element becomes a node exactly once and no array is copied: O(n) time, and the recursion is only about log n deep, so the extra space (besides the tree itself) is O(log n).

TimeO(n)

SpaceO(log n)