Home | Projects | Notes > Problem Solving > LC - E - 108. Convert Sorted Array to Binary Search

LC - E - 108. Convert Sorted Array to Binary Search

Solutions in C++

Solution 1

To create a height-balanced binary search tree (BST) from a sorted array, we need to maintain an equal depth across the tree, so both left and right subtrees are as close in height as possible. The best way to achieve this is by choosing the middle element of the array as the root, ensuring the left half of the array will form the left subtree and the right half will form the right subtree. Recursively applying this approach ensures the resulting tree is both height-balanced and sorted according to BST properties.

Approach

1. Choose the middle element as root:

   For each segment of the array, pick the middle element. This divides the array into two halves that will become the left and right subtrees.

2. Recursive division:

   • Recursively build the left subtree using the left half of the array.

   • Recursively build the right subtree using the right half of the array.

3. Base case:

   If the current segment is empty, return null, as there are no more elements to process.

Complexity Analysis:

• $T=O(n)$$T=O(n)$

• $S=O(n)$$S=O(n)$

Solution:

33
1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    TreeNode* sortedArrayToBST(vector<int>& nums) {
15
        return helper(nums, 0, nums.size() - 1);
16
    }
17

18
private:
19
    TreeNode* helper(vector<int>& nums, int left, int right)
20
    {
21
        if (left > right)
22
            return nullptr;
23
        
24
        int mid = left + (right - left) / 2;
25

26
        TreeNode *root = new TreeNode(nums[mid]);
27

28
        root->left = helper(nums, left, mid - 1);
29
        root->right = helper(nums, mid + 1, right);
30

31
        return root;
32
    }
33
};

L24: This is to avoid int overflow in case of very large values. (e.g., during the calculation of (left + right) / 2, int overflow can occur.)

This approach ensures the creation of a balanced BST with O(n) complexity, as each element in the array is processed once. By choosing the middle element as the root and recursively applying the same process to each half of the array, we ensure the final tree is balanced and sorted as required for a BST.