Convert a Sorted Array to a Balanced BST in C++

Introduction

A Balanced Binary Search Tree (BST) is a binary tree in which the depth of the two subtrees of every node never differs by more than 1. Given a sorted array, we can create a balanced BST by ensuring that the middle element of the array becomes the root, and recursively applying the same process for the left and right halves of the array. This guarantees that the resulting tree will be height-balanced.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure representing each node in the BST.
2. Write a recursive function sortedArrayToBST that takes a sorted array and converts it to a balanced BST.
3. The function picks the middle element as the root and recursively builds the left and right subtrees using the left and right halves of the array.

Code Implementation

// C++ program to convert a sorted array to a balanced BST

#include <iostream>
#include <vector>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Recursive function to convert sorted array to a balanced BST
TreeNode* sortedArrayToBST(vector<int>& nums, int start, int end) {
    // Base case: if the array range is invalid, return NULL
    if (start > end)
        return NULL;

    // Find the middle element of the current subarray
    int mid = start + (end - start) / 2;

    // Create a new tree node with the middle element
    TreeNode* node = new TreeNode(nums[mid]);

    // Recursively construct the left subtree from the left half of the array
    node->left = sortedArrayToBST(nums, start, mid - 1);

    // Recursively construct the right subtree from the right half of the array
    node->right = sortedArrayToBST(nums, mid + 1, end);

    // Return the current node (root of the subtree)
    return node;
}

// Helper function to initiate the conversion from sorted array to BST
TreeNode* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBST(nums, 0, nums.size() - 1);
}

// Helper function to perform in-order traversal of the BST
void inOrderTraversal(TreeNode* root) {
    if (!root) return;

    // Traverse the left subtree
    inOrderTraversal(root->left);

    // Print the node's value
    cout << root->val << " ";

    // Traverse the right subtree
    inOrderTraversal(root->right);
}

int main() {
    // Example sorted array
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};

    // Convert sorted array to a balanced BST
    TreeNode* root = sortedArrayToBST(nums);

    // Perform in-order traversal to display the BST
    cout << "In-order Traversal of the Balanced BST: ";
    inOrderTraversal(root);
    cout << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary search tree. Each node stores a value val and pointers to its left and right children.
2. sortedArrayToBST function: This is a recursive function that converts the sorted array into a balanced BST. It picks the middle element of the array (or subarray) as the root and recursively builds the left and right subtrees.
3. sortedArrayToBST helper function: This function simply initiates the recursive process by calling the main function with the start and end indices of the array.
4. inOrderTraversal function: This function performs an in-order traversal (left subtree, root, right subtree) of the BST, ensuring that the elements are printed in sorted order.

How the Algorithm Works

The key to creating a balanced BST from a sorted array is choosing the middle element of the array (or subarray) as the root. The elements to the left of the middle element will become the left subtree, and the elements to the right will become the right subtree.

This approach ensures that both the left and right subtrees are approximately the same height, resulting in a balanced tree.

The recursion terminates when the subarray becomes empty (i.e., when the start index is greater than the end index).

Sample Output

If you run the above program with the example array {1, 2, 3, 4, 5, 6, 7}, the output will be:

In-order Traversal of the Balanced BST: 1 2 3 4 5 6 7

The in-order traversal confirms that the tree is a valid BST, as it prints the elements in ascending order.

Conclusion

This algorithm is an efficient way to convert a sorted array into a balanced BST. The time complexity of the algorithm is O(N), where N is the number of elements in the array, since each element is processed once. The space complexity is O(log N) due to the recursive calls, which corresponds to the height of the tree.

By using the middle element as the root at each step, we ensure that the tree remains balanced, leading to optimal performance for subsequent operations like searching, insertion, and deletion.