Leetcode: 08. Convert Sorted Array to Binary Search Tree

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.