### Leetcode: 08. Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree: Efficient Implementation

# Convert Sorted Array to Binary Search Tree: Efficient Implementation

## Algorithm Explanation

The given code snippet implements the solution to the problem "Convert Sorted Array to Binary Search Tree." Let's break down the implementation:

```    ```

#include <vector>

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

class Solution {
private:
std::vector<int> nums;

public:
TreeNode* sortedArrayToBST(std::vector<int>& nums) {
this->nums = nums;
return helper(0, nums.size() - 1);
}

TreeNode* helper(int left, int right) {
if (left > right)
return nullptr;

int partition = (left + right) / 2;

TreeNode* root = new TreeNode(nums[partition]);
root->left = helper(left, partition - 1);
root->right = helper(partition + 1, right);
return root;
}
};

int main() {
Solution solution;
std::vector<int> nums = {-10, -3, 0, 5, 9};
TreeNode* root = solution.sortedArrayToBST(nums);

// Perform operations on the constructed BST if needed

return 0;
}

```
```

## Example

Let's consider an example to understand how the algorithm works:

```    ```

Solution solution;
std::vector<int> nums = {-10, -3, 0, 5, 9};
TreeNode* root = solution.sortedArrayToBST(nums);

```
```

The input array `nums` is `{-10, -3, 0, 5, 9}`. After calling `sortedArrayToBST`, the algorithm will construct the following Binary Search Tree:

```    ```

0
/ \
-3   9
/   /
-10   5

```
```

The resulting `root` node will point to the root of the BST.

## Complexity Analysis

Let's analyze the time and space complexities of the algorithm:

• Time Complexity: The algorithm performs a binary search on the sorted array, resulting in a time complexity of O(log N) for each element. Since there are N elements in the array, the overall time complexity is O(N log N).
• Space Complexity: The algorithm uses recursion to construct the BST, resulting in a space complexity of O(log N) due to the recursive call stack. Additionally, the `nums` vector requires O(N) space. Hence, the overall space complexity is O(N).

## Conclusion

In this blog post, we explored an efficient algorithm to convert a sorted array into a Binary Search Tree (BST). The provided code snippet demonstrates the implementation, along with examples and complexity analysis. Feel free to copy the code or use it as a reference for your own projects.