Sorted Array To Binary Search Tree

A Binary Search Tree (BST) is a widely used data structure in computer science and programming. It is a binary tree with a special property that makes it particularly useful for efficient searching and sorting operations. The key property of a BST is that for each node:

All nodes in its left subtree have values less than or equal to the node's value.
All nodes in its right subtree have values greater than the node's value.

This property ensures that the BST maintains a specific order among its elements, making it possible to perform efficient operations like searching, insertion, and deletion.

Please visit our Tree Visualizer and Converter to visualize the sample input of binary tree and graph to solve the questions.

Algorithm

The algorithm for converting a sorted array into a balanced BST is straightforward. We'll use a recursive approach to divide the array into two halves and select the middle element as the root of the BST. Then, we'll recursively apply the same process to the left and right halves of the array to build the left and right subtrees.

Find the middle element of the sorted array. This element will be the root of the BST.
Recursively construct the left subtree from the left half of the array (elements less than the middle element).
Recursively construct the right subtree from the right half of the array (elements greater than the middle element).

This order ensures that nodes are visited in ascending order when dealing with binary search trees.

Code Example

// C++ Code
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBST(nums, left, mid - 1);
        root->right = sortedArrayToBST(nums, mid + 1, right);
        
        return root;
    }
    
    // Helper function to print the tree (in-order traversal)
    void inOrderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        inOrderTraversal(root->left);
        cout << root->val << " ";
        inOrderTraversal(root->right);
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    TreeNode* root = solution.sortedArrayToBST(nums);
    solution.inOrderTraversal(root); // Print the sorted BST
    return 0;
}

Code Explained:

In this blog post, we discussed the algorithm for converting a sorted array into a binary search tree (BST) and provided code examples in Java, C++, and JavaScript. This algorithm is a fundamental building block for many tree-based data structures and algorithms. Converting a sorted array into a BST allows us to efficiently search for values in a balanced and organized manner.