Convert Sorted Array to Binary Search Tree

Given a sorted array of integers, construct a binary search tree (BST) such that the tree is balanced. A balanced BST is one where the depth of the two subtrees of every node never differs by more than one. This is a fundamental problem in data structures and algorithms, as efficiently converting sorted data into a BST allows for logarithmic time complexity for search, insertion, and deletion operations.

Problem Description

Your task is to write a function that takes a sorted array of unique integers and converts it into a height-balanced Binary Search Tree.

Key Requirements:

• The function should return the root node of the constructed BST.
• The resulting BST must be height-balanced. This means that for every node, the height of its left subtree and the height of its right subtree differ by at most 1.
• All nodes in the left subtree of a node must contain values less than the node's value.
• All nodes in the right subtree of a node must contain values greater than the node's value.
• The input array is guaranteed to be sorted in ascending order and contain unique integers.

Expected Behavior:

When given a sorted array, your function should create a BST that satisfies the BST properties and is height-balanced. There might be multiple valid height-balanced BSTs for a given input array; any one of them is acceptable.

Edge Cases:

• An empty input array.
• An input array with a single element.

Examples

Example 1:

Input: [-10, -3, 0, 5, 9]
Output:
    0
   / \
 -3   9
 /   /
-10 5
Explanation:
The middle element (0) is chosen as the root.
The left subarray [-10, -3] forms the left subtree, with -3 as its root.
The right subarray [5, 9] forms the right subtree, with 9 as its root.
This results in a height-balanced BST.

Example 2:

Input: [1, 3]
Output:
    3
   /
  1
Explanation:
The middle element (3, or 1 depending on implementation choice) can be the root.
If 3 is the root, 1 becomes its left child. This is a valid height-balanced BST.
Alternatively, if 1 is the root, 3 becomes its right child, also valid.

Example 3:

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

Constraints

• The number of elements in the array will be between 0 and 1000.
• The values in the array will be within the range of -10^9 to 10^9.
• The array is sorted in ascending order and contains unique integers.
• Your solution should aim for an efficient time complexity, ideally O(N), where N is the number of elements in the array.

Notes

A common strategy to ensure a balanced BST from a sorted array is to recursively select the middle element of the current subarray as the root of the subtree being constructed. The left half of the subarray will then form the left subtree, and the right half will form the right subtree.

You will need to define a TreeNode structure (or equivalent) to represent the nodes of your binary tree, typically containing a value, a left child pointer, and a right child pointer.