5.7 Convert Sorted Array to BST

5.7.1 Problem Metadata

5.7.2 Description

Convert a sorted array to a height-balanced BST.

5.7.3 Examples

Example 1: Array with Odd Length

Input: nums = [-10,-3,0,5,9]
Output:
    0
   / \
 -3   9
 /   /
-10 5
Explanation: Middle element (0) becomes root; recurse on left and right halves

Example 2: Array with Even Length

Input: nums = [1,3]
Output:
  3
 /
1
(or vice versa, both are valid height-balanced BSTs)

Example 3: Single Element

Input: nums = [1]
Output: 1

5.7.4 Constraints

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

5.7.5 Solution - Divide and Conquer

5.7.5.1 Walkthrough

To build a height-balanced BST from a sorted array, use the middle element as the root. This ensures the tree remains balanced since it divides the remaining elements equally between left and right subtrees:

  1. Base case: If left > right, return null (no elements).
  2. Find middle: Calculate mid = left + (right - left) / 2 to avoid integer overflow.
  3. Create root: Use nums[mid] as the current node.
  4. Recurse left: Recursively build left subtree from nums[left…mid-1].
  5. Recurse right: Recursively build right subtree from nums[mid+1…right].
  6. The middle element selection ensures all left subtree values < root < all right subtree values (BST property).

5.7.5.2 Analysis

  • Time Complexity: O(n) — each element is visited once
  • Space Complexity: O(log n) — recursion stack depth for balanced tree (O(n) in worst case)

5.7.5.3 Implementation Steps

  1. Define a recursive helper function with left and right indices
  2. Handle base case when left > right
  3. Calculate middle index
  4. Create node with middle value
  5. Recursively build left subtree (left to mid-1)
  6. Recursively build right subtree (mid+1 to right)
  7. Return the constructed node

5.7.5.4 Code - Java

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

private TreeNode build(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
    int mid = left + (right - left) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = build(nums, left, mid - 1);
    node.right = build(nums, mid + 1, right);
    return node;
}