Convert Sorted Array to Binary Search Tree

This challenge asks you to build a Binary Search Tree (BST) from a sorted array. BSTs are fundamental data structures used in many algorithms and applications, and this problem tests your ability to efficiently construct one from a pre-sorted input. Successfully solving this problem demonstrates understanding of recursion and tree construction.

Problem Description

You are given a sorted array of integers. Your task is to convert this sorted array into a balanced Binary Search Tree (BST). A balanced BST is one where the left and right subtrees of every node have approximately the same number of nodes. The root of the BST should be the middle element of the sorted array. The left subtree should be constructed from the elements to the left of the middle element, and the right subtree from the elements to the right.

What needs to be achieved:

• Create a BST where each node's value is an element from the input array.
• The BST must adhere to the BST property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.
• The BST should be as balanced as possible, using the middle element of the sorted array as the root.

Key Requirements:

• The input array will always be sorted in ascending order.
• The output should be a representation of the constructed BST (the specific representation depends on the language you choose - a tree node class/structure is expected).
• The BST should be balanced.

Expected Behavior:

Given a sorted array, the function should return the root node of the constructed BST. If the input array is empty, the function should return null or an equivalent representation of an empty tree.

Edge Cases to Consider:

• Empty input array.
• Input array with a single element.
• Arrays with even numbers of elements (in this case, either of the two middle elements can be chosen as the root).

Examples

Example 1:

Input: [-10, -3, 0, 5, 9]
Output: A BST with root node having value 0, left subtree rooted at -3, and right subtree rooted at 5.
Explanation: The middle element is 0. The left half [-10, -3] becomes the left subtree, and the right half [5, 9] becomes the right subtree.  Each half is recursively processed to build the subtrees.

Example 2:

Input: [1, 3]
Output: A BST with root node having value 3, left subtree rooted at 1.
Explanation: The middle element is 3. The left half [1] becomes the left subtree. The right half is empty.

Example 3:

Input: []
Output: null
Explanation: An empty array results in an empty tree.

Constraints

• The input array will contain integers.
• The length of the input array can range from 0 to 1000.
• The time complexity of your solution should be O(n), where n is the length of the input array. This is because each element should be visited and used exactly once.
• The space complexity of your solution should be O(n) in the worst case (e.g., a skewed tree).

Notes

• A recursive approach is generally the most straightforward way to solve this problem.
• Consider how to handle the base case (empty subarray) in your recursion.
• Think about how to find the middle element of the array efficiently. You can use integer division to find the middle index.
• The "balanced" requirement means that the root should be the middle element, but you don't need to explicitly check for perfect balance after construction. The recursive approach naturally leads to a reasonably balanced tree.