Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are 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: [0,-10,5,null,-3,null,9] is also accepted.

Example 2:

Input: nums = [1,3] Output: [3,1] Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in a strictly increasing order.

Approach: Recursion with Middle Element as Root (Optimal Solution)

Algorithm

1. Define a recursive function dfs(l, r) that builds the subtree from the index range [l, r]
2. If l > r, return null
3. Pick the middle element at mid = (l + r) / 2 as the root
4. Recursively build the left subtree from [l, mid - 1] and the right subtree from [mid + 1, r]
5. Attach the subtrees and return the root

Key Insight

A binary search tree built from a sorted array keeps the BST property if the root splits the array at the middle: everything to the left is smaller and everything to the right is larger. Choosing the middle guarantees the left and right halves are the same size (differ by at most one), which makes the tree height-balanced.

Time & Space Complexity

• Time Complexity: O(n) - every element is visited once
• Space Complexity: O(log n) - recursion stack depth equals the tree height, which is O(log n) for a balanced tree

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class ConvertSortedArrayToBinarySearchTree {

    private int[] nums;

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0, nums.length - 1);
    }

    private TreeNode dfs(int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) >>> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(l, mid - 1);
        root.right = dfs(mid + 1, r);
        return root;
    }
}

Example Walkthrough

For nums = [-10,-3,0,5,9]:

1. dfs(0, 4): mid = 2, root = 0
2. dfs(0, 1): mid = 0, root = -10, right subtree = dfs(1, 1) = node -3
3. dfs(3, 4): mid = 3, root = 5, right subtree = dfs(4, 4) = node 9
4. Result: 0 with left subtree (-10, right=-3) and right subtree (5, right=9) → [0,-3,9,-10,null,5]

Key Insights

1. Middle Splitting: The middle element is the root of every subtree, keeping it balanced
2. Divide and Conquer: Each element becomes the root of its own range, splitting the problem into two halves
3. Balanced Guarantee: Halves differ in size by at most one element, so height stays O(log n)
4. Multiple Valid Answers: Any middle pick (left-middle or right-middle) yields a valid height-balanced BST

The recursive divide-and-conquer approach is the optimal solution, providing O(n) time and O(log n) space.