🔥 [VIDEO] Converting Sorted Array to Balanced Binary Search Tree 🌳
Intuition\nUpon reading the problem, it became clear that a binary search tree (BST) could be formed by leveraging the property of a sorted array, where the mid
# Intuition\nUpon reading the problem, it became clear that a binary search tree (BST) could be formed by leveraging the property of a sorted array, where the middle element can serve as the root of the BST. This is because in a sorted array, elements to the left of the middle element are lesser, and elements to the right are greater, which aligns with the properties of a BST.\n\nhttps://youtu.be/JiH4MDE2sJE\n\n# Approach\nThe approach to solving this problem involves recursion. The main idea is to find the middle element of the array. This middle element will become the root of our binary search tree because it ensures that the tree will remain balanced. The left half of the array will be used to build the left subtree, and similarly, the right half for the right subtree. We then recursively construct these subtrees.\n\n# Complexity\n- Time complexity: The time complexity for this approach is \\(O(n)\\), where \\(n\\) is the number of elements in the array. This is because we are visiting each element once while constructing the BST.\n\n- Space complexity: The space complexity is \\(O(n)\\) as well. This is because, in the worst-case scenario, we could end up with a recursive call stack depth of \\(n\\) during the creation of the BST.\n\n# Code\n``` Python []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n        if not nums: \n            return None \n        mid = len(nums) // 2 \n        # create node and construct subtrees \n        node = TreeNode(nums[mid]) \n        node.left = self.sortedArrayToBST(nums[:mid]) \n        node.right = self.sortedArrayToBST(nums[mid+1:]) \n        return node \n```\n``` JavaScript []\nvar sortedArrayToBST = function(nums) {\n    if(!nums.length) return null;\n    let mid = Math.floor(nums.length / 2);\n    let root = new TreeNode(nums[mid]);\n    root.left = sortedArrayToBST(nums.slice(0, mid));\n    root.right = sortedArrayToBST(nums.slice(mid + 1));\n    return root;\n};\n```     \n``` C# []\npublic class Solution {\n    public TreeNode SortedArrayToBST(int[] nums) {\n        if(nums == null || nums.Length == 0)\n            return null;\n        return constructBSTRecursive(nums, 0, nums.Length - 1);\n    }\n\n    private TreeNode constructBSTRecursive(int[] nums, int left, int right) {\n        if(left > right)\n            return null;\n        int mid = left + (right - left) / 2;\n        TreeNode node = new TreeNode(nums[mid]);\n        node.left = constructBSTRecursive(nums, left, mid - 1);\n        node.right = constructBSTRecursive(nums, mid + 1, right);\n        return node;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    TreeNode* sortedArrayToBST(vector<int>& nums) {\n        return constructBSTRecursive(nums, 0, nums.size() - 1);\n    }\n\n    TreeNode* constructBSTRecursive(vector<int>& nums, int left, int right) {\n        if(left > right)\n            return NULL;\n        int mid = left + (right - left) / 2;\n        TreeNode* node = new TreeNode(nums[mid]);\n        node->left = constructBSTRecursive(nums, left, mid - 1);\n        node->right = constructBSTRecursive(nums, mid + 1, right);\n        return node;\n    }\n};\n```\n``` Java []\npublic class Solution {\n    public TreeNode sortedArrayToBST(int[] nums) {\n        if(nums == null || nums.length == 0)\n            return null;\n        return constructBSTRecursive(nums, 0, nums.length - 1);\n    }\n\n    private TreeNode constructBSTRecursive(int[] nums, int left, int right) {\n        if(left > right)\n            return null;\n        int mid = left + (right - left) / 2;\n        TreeNode node = new TreeNode(nums[mid]);\n        node.left = constructBSTRecursive(nums, left, mid - 1);\n        node.right = constructBSTRecursive(nums, mid + 1, right);\n        return node;\n    }\n}\n```\nRemember, practicing and understanding the underlying concepts is key to mastering data structures and algorithms. Happy coding!
['C++', 'Java', 'Python3', 'JavaScript', 'C#']