Problem Statement

Given a sorted array of integers, the task is to construct a balanced Binary Search Tree (BST) from the array elements.

Examples:

Let's consider some examples to understand the problem better.

Example 1:

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

Output:

      0
     / \
   -3   9
  /   /
-10   5

Example 2:

Input: [1, 3, 5, 7, 9, 11]

Output:

    5
   / \
  1   9
   \  / \
   3  7  11

Theory:

Before diving into the approaches to solve the problem, let's understand some key concepts:

Binary Search Tree:

A binary tree in which each node has at most two children, and for each node, all elements in the left subtree are less than the node's value, and all elements in the right subtree are greater than the node's value.

Balanced BST:

A BST is balanced if the height of the left and right subtrees of every node differs by at most one. A balanced BST ensures efficient search, insert, and delete operations with a time complexity of O(log n), where n is the number of nodes.

Different Approaches

1 Recursive Approach:

Intuition:

The recursive approach leverages the concept of binary search. Since the given array is sorted, selecting the middle element ensures that the resulting BST is balanced. Each time we select the middle element as the root, the left half of the array contributes to the left subtree, and the right half contributes to the right subtree. This process is recursively applied to construct the entire BST.

Algorithm:

constructBST(nums, left, right):
    if left > right:
        return nullptr
    mid = left + (right - left) / 2
    root = new TreeNode(nums[mid])
    root->left = constructBST(nums, left, mid - 1)
    root->right = constructBST(nums, mid + 1, right)
    return root

Code Implementation

1 Recursive Approach:

#include <iostream>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to convert sorted array to BST
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // Call the recursive function to construct the BST
        return constructBST(nums, 0, nums.size() - 1);
    }
    
    // Recursive function to construct BST
    TreeNode* constructBST(vector<int>& nums, int left, int right) {
        // Base case: If left index is greater than right index, return nullptr
        if (left > right) return nullptr;
        
        // Calculate the middle index
        int mid = left + (right - left) / 2;
        
        // Create a new TreeNode with the value at the middle index
        TreeNode* root = new TreeNode(nums[mid]);
        
        // Recursively construct left subtree from left to mid - 1
        root->left = constructBST(nums, left, mid - 1);
        
        // Recursively construct right subtree from mid + 1 to right
        root->right = constructBST(nums, mid + 1, right);
        
        // Return the root of the constructed subtree
        return root;
    }
};

// Helper function to perform inorder traversal of BST
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    // Traverse left subtree
    inorderTraversal(root->left);
    // Print the value of the current node
    cout << root->val << " ";
    // Traverse right subtree
    inorderTraversal(root->right);
}

int main() {
    Solution solution;
    vector<int> nums = {-10, -3, 0, 5, 9};
    // Convert sorted array to BST
    TreeNode* root = solution.sortedArrayToBST(nums);
    cout << "Inorder Traversal of the constructed BST:" << endl;
    // Print inorder traversal of the constructed BST
    inorderTraversal(root);
    return 0;
}

Explanation:

• We define a TreeNode struct to represent the nodes of the binary tree.
• The Solution class contains the sortedArrayToBST function, which is the entry point for converting the sorted array to a Binary Search Tree (BST).
• Inside the sortedArrayToBST function, we call the constructBST function, passing the sorted array nums along with the indices left and right.
• The constructBST function is a recursive function that constructs the BST using the divide-and-conquer approach.
• In each recursive call, we calculate the middle index (mid) of the current range (left to right), and create a new TreeNode with the value at index mid.
• We then recursively call constructBST for the left half of the array (from left to mid - 1) and assign the returned TreeNode as the left child of the current node.
• Similarly, we recursively call constructBST for the right half of the array (from mid + 1 to right) and assign the returned TreeNode as the right child of the current node.
• The recursion stops when the base case is reached, i.e., when left is greater than right, in which case we return nullptr.
• Finally, we print the inorder traversal of the constructed BST to verify its correctness.

Complexity Analysis

1 Recursive Approach:

Time Complexity: O(n)

• The time complexity of this approach is O(n), where n is the number of elements in the input sorted array.
• Each element in the array is visited exactly once, and for each element, a constant amount of work is done.
• Hence, the overall time complexity is linear, O(n).

Space Complexity: O(n)

• The space complexity of this approach is also O(n).
• This is because the recursive calls consume space on the call stack, and in the worst case, the maximum depth of the recursion is n (if the tree is completely unbalanced).
• Therefore, the overall space complexity is linear, O(n)