Convert Sorted Array to Binary Search Tree

Problem Statement

Given an integer array named nums, where the numbers are organized in an ascending order, the task is to convert this array into a height-balanced binary search tree (BST). A height-balanced BST is one in which the depth of the two subtrees of every node never differ by more than one. This balance is crucial for ensuring that operations such as search, insert, and delete can be performed efficiently (in logarithmic time complexity) relative to the height of the tree.

Examples

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.

Approach and Intuition

The approach for converting a sorted array into a height-balanced BST leverages the properties of binary search due to the sorted nature of the array. Here is the step-by-step process:

1. Identify the middle element of the array to be the root of the BST:

   • This helps in maintaining the balance as it ensures that the number of nodes on the left and right subtrees are as equal as possible.

2. Recursively apply the same process to the left half of the array to construct the left subtree.

   • The middle element of this left subsection becomes the left child of the root.

3. Recursively apply the same process to the right half of the array to construct the right subtree.

   • The middle element of this right subsection becomes the right child of the root.

4. Continue this division until each subsection cannot be divided further (i.e., it becomes a single element or empty), at which point the recursion ends.

Through this recursive divide-and-conquer strategy, the constructed BST naturally remains height-balanced. Each recursive step selects a new root that balances the number of nodes in the left and right subtrees of that particular subtree, contributing to the overall balance of the tree.

• Example 1 from the problem statement illustrates this:

  • The array [-10, -3, 0, 5, 9] has 0 as its middle element. The subtrees rooted at -3 (left) and 9 (right) are recursively constructed using the same strategy.
  • Although the exact left-right arrangement might differ (as the explanation allows two structures), both are valid height-balanced BSTs.

• Example 2 shows that smaller trees (like those with 2 elements) can also follow the rule by taking the last element as the root (to ensure at most one level of depth difference), demonstrating the flexibility and correctness of the approach across varied input sizes.

This methodical conversion guarantees the height-balancing of the resultant BST, promoting operations within optimal time complexities tied to the tree's height. The constraints ensure the handling of reasonably large inputs, validating this efficient approach for substantial datasets.

Solutions

class Solution {
public:
    TreeNode* transformSortedArrayToBST(vector<int>& arr) {
        return buildBST(arr, 0, arr.size() - 1);
    }
    
private:
    TreeNode* buildBST(vector<int>& arr, int start, int end) {
        if (start > end) return nullptr;
        int middle = (start + end) / 2;
        if ((start + end) % 2 == 1) middle += rand() % 2;
        TreeNode* node = new TreeNode(arr[middle]);
        node->left = buildBST(arr, start, middle - 1);
        node->right = buildBST(arr, middle + 1, end);
        return node;
    }
};