Convert Sorted Array to Binary Search Tree

Description

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 <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

---

Recursive Divide & Conquer ($O(N)$ Time, $O(\log N)$ Space)

Intuition

To construct a height-balanced BST, the middle element of any sorted sub-array must be selected as the root node:

1. Calculate mid = left + (right - left) / 2.
2. Instantiate TreeNode(nums[mid]) as the root of the current subtree.
3. Pass index pointers left and right to recursively construct:
   • Left subtree from index left to mid - 1.
   • Right subtree from index mid + 1 to right.
4. Interview Pitch: Avoid using Arrays.copyOfRange() to slice arrays, as creating sub-arrays at each step adds unnecessary $O(N\log N)$ time and $O(N)$ memory overhead. Index pointers keep it at optimal $O(N)$ time and $O(\log N)$ auxiliary space.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }
 
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;
 
        // Pick the middle element to ensure height balance
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
 
        // Recursively build subtrees using index boundaries
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every element in nums is visited once to instantiate its tree node.
• Space Complexity: $O(\log N)$ — The tree is strictly height-balanced, so maximum call stack depth is $\lceil {\log }_{2}N\rceil$.

---

Easy Memory Rule

“Pick mid as Root $\to$ Pass left to mid - 1 for Left Subtree $\to$ Pass mid + 1 to right for Right Subtree!”