Array to BST

Given a sorted array. Convert it into a Height Balanced Binary Search Tree (BST). Return the root of the BST.

Height-balanced BST means a binary tree in which the depth of the left subtree and the right subtree of every node never differ by more than 1.

Note: The driver code will check the BST, if it is a Height-balanced BST, the output will be true otherwise the output will be false.

Examples :

Input: nums = [1, 2, 3, 4]
Output: true
Explanation: The preorder traversal of the following BST formed is [2, 1, 3, 4]:
           2
         /   \
        1     3
               \
                4

Input: nums = [1, 2, 3, 4, 5, 6, 7]
Ouput: true
Explanation: The preorder traversal of the following BST formed is [4, 2, 1, 3, 6, 5, 7]:
        4
       / \
      2   6
     / \   / \
    1 3  5 7

Expected Time Complexity: O(n)
Expected Auxillary Space: O(n)

Constraints:
1 ≤ nums.size() ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Approach 01

class Solution {
public:
    // Recursive function to construct a balanced BST from a sorted array
    Node* buildBSTFromSortedArray(vector<int>& nums, int start, int end) {
        if (start > end) {
            return NULL; // Base case: no elements to process
        }
        
        int mid = (start + end) / 2; // Find the middle index
        Node* root = new Node(nums[mid]); // Create a new node with the middle element
        
        // Recursively build the left and right subtrees
        root->left = buildBSTFromSortedArray(nums, start, mid - 1);
        root->right = buildBSTFromSortedArray(nums, mid + 1, end);
        
        return root; // Return the root of the subtree
    }

    // Function to convert a sorted array to a balanced BST
    Node* sortedArrayToBST(vector<int>& nums) {
        int start = 0; // Starting index of the array
        int end = nums.size() - 1; // Ending index of the array
        return buildBSTFromSortedArray(nums, start, end); // Build and return the BST
    }
};

class Solution:
    # Recursive function to construct a balanced BST from a sorted array
    def buildBSTFromSortedArray(self, nums, start, end):
        if start > end:
            return None  # Base case: no elements to process
        
        mid = (start + end) // 2  # Find the middle index
        root = Node(nums[mid])  # Create a new node with the middle element
        
        # Recursively build the left and right subtrees
        root.left = self.buildBSTFromSortedArray(nums, start, mid - 1)
        root.right = self.buildBSTFromSortedArray(nums, mid + 1, end)
        
        return root  # Return the root of the subtree

    # Function to convert a sorted array to a balanced BST
    def sortedArrayToBST(self, nums):
        start = 0  # Starting index of the array
        end = len(nums) - 1  # Ending index of the array
        return self.buildBSTFromSortedArray(nums, start, end)  # Build and return the BST

Time Complexity

• Recursive Calls:

  The function buildBSTFromSortedArray is called recursively to construct the BST. Each recursive call processes a subarray that is roughly half the size of the previous one. This results in a time complexity of \( O(\log n) \) levels of recursion, where \( n \) is the number of elements in the array.

• Processing Each Element:

  Each element in the array is processed exactly once, as each element is used to create a node in the BST. Thus, the overall time complexity is \( O(n) \), where \( n \) is the number of elements in the input array.

• Overall Time Complexity:

  Combining the recursive call overhead with the processing of each element, the overall time complexity is \( O(n) \), as the \( O(\log n) \) recursion depth is dominated by the \( O(n) \) processing step.

Space Complexity

• Recursive Stack Space:

  The maximum depth of the recursion stack is \( O(\log n) \) due to the binary splitting of the array. This contributes \( O(\log n) \) space complexity.

• Auxiliary Space:

  Additional space is used to store the nodes of the BST. This space is \( O(n) \) for the nodes themselves, as there is a node for each element in the array.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is the number of elements in the input array. This includes both the space required for the recursion stack and the space for storing the BST nodes.