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

    public TreeNode yo(int nums[], int l, int h) {
        if (l > h)
            return null;
        int mid = (l + h) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = yo(nums, l, mid - 1);
        root.right = yo(nums, mid + 1, h);
        return root;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The problem of "Convert Sorted Array to Binary Search Tree" involves taking a sorted (non-decreasing) array and converting it into a balanced Binary Search Tree (BST). The key challenge here is to ensure that the resulting binary search tree is balanced. A balanced binary search tree means that the left and right subtrees of every node differ in height by at most 1.

The goal is to maintain the sorted order of the array while ensuring the tree is height-balanced. This problem can be approached using the divide-and-conquer strategy by selecting the middle element of the array as the root, and recursively constructing the left and right subtrees.

Problem Statement

Given a sorted array, you need to convert it into a height-balanced binary search tree (BST). The binary search tree should be constructed such that the middle element of the array is the root, the left subtree is built from the left half of the array, and the right subtree is built from the right half of the array.

The binary search tree is represented by a tree node structure, and you are required to implement a function that builds the tree.

Approach

The solution to this problem is straightforward if we consider the following approach:

Use a recursive strategy to divide the sorted array into smaller subarrays.
For each subarray, select the middle element as the root of the subtree.
Recurse on the left and right halves of the array to build the left and right subtrees, respectively.
This will ensure that the resulting tree is balanced, as we always select the middle element as the root.

This approach follows the divide-and-conquer paradigm. The middle element is chosen to minimize the height of the tree, ensuring that the tree remains balanced.

Algorithm

The algorithm can be described in the following steps:

Find the middle element of the array.
Create a new tree node with the middle element as the root.
Recursively repeat the process for the left and right halves of the array to construct the left and right subtrees.
Return the root node once all the subtrees are constructed.

The algorithm ensures that each node is added to the tree in a balanced manner by always selecting the middle element of the array as the root.

Example

Consider the following sorted array:

        [-10, -3, 0, 5, 9]

We will convert this array into a balanced binary search tree:

- The middle element of the array is 0, so 0 becomes the root of the tree. - The left subtree is built from the left half of the array [-10, -3], with -3 as the root. - The right subtree is built from the right half of the array [5, 9], with 9 as the root, and 5 as its left child. - This results in a balanced binary search tree.

Code Implementation

Below is the Python implementation of the algorithm to convert a sorted array into a balanced binary search tree:

- We first check if the input array is empty. If it is, we return None (no tree). - We calculate the middle index of the array, and create a TreeNode with the value at the middle index. - We then recursively build the left and right subtrees using the left and right halves of the array. - Finally, we return the root node of the tree.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the array. This is because, for each node, we are processing the entire array exactly once in the recursive calls.

The space complexity is O(log n) due to the recursive call stack. In the worst case, the height of the tree is log(n), and this is the depth of recursion. The space complexity can also be considered O(n) if we account for the space used by the tree itself.

Conclusion

The "Convert Sorted Array to Binary Search Tree" problem demonstrates how the divide-and-conquer approach can be used to construct a balanced binary search tree from a sorted array. By always selecting the middle element as the root and recursively building subtrees, we ensure the tree is balanced, which is a key characteristic of a binary search tree. This problem is a useful exercise in understanding recursion and tree construction.