✅ 🔥 0 ms Runtime Beats 100% User 🔥|| Step By Steps Solution ✅ ||  Easy to Understand  ✅🔥 ||
\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Intuition :\nTo create a height-balanced binary search tree (BST) from a sorted arra
\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Intuition :\nTo 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.\n\n### Approach :\n1. **Choose the Middle Element as Root**:\n   - 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.\n2. **Recursive Division**:\n   - Recursively build the left subtree using the left half of the array.\n   - Recursively build the right subtree using the right half of the array.\n3. **Base Case**:\n   - If the current segment is empty, return `null`, as there are no more elements to process.\n\n### Solving Steps :\n1. Start with the whole array and calculate the middle index.\n2. Create a new tree node with the middle element as the value.\n3. Recursively apply the same approach to the left and right halves of the array.\n4. Attach the recursively created left and right nodes to the root node.\n5. Return the root of the tree.\n\n### Code Implementation :\n\n#### Java\n```java\n// Definition for a binary tree node.\npublic class TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n    TreeNode() {}\n    TreeNode(int val) { this.val = val; }\n    TreeNode(int val, TreeNode left, TreeNode right) {\n        this.val = val;\n        this.left = left;\n        this.right = right;\n    }\n}\n\nclass Solution {\n    public TreeNode sortedArrayToBST(int[] nums) {\n        return helper(nums, 0, nums.length - 1);\n    }\n\n    private TreeNode helper(int[] nums, int left, int right) {\n        if (left > right) return null;\n        int mid = (left + right) / 2;\n        TreeNode root = new TreeNode(nums[mid]);\n        root.left = helper(nums, left, mid - 1);\n        root.right = helper(nums, mid + 1, right);\n        return root;\n    }\n}\n\n```\n\n#### C++\n```cpp\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    TreeNode* sortedArrayToBST(vector<int>& nums) {\n        return helper(nums, 0, nums.size() - 1);\n    }\n\nprivate:\n    TreeNode* helper(vector<int>& nums, int left, int right) {\n        if (left > right) return nullptr;\n        int mid = left + (right - left) / 2;\n        TreeNode* root = new TreeNode(nums[mid]);\n        root->left = helper(nums, left, mid - 1);\n        root->right = helper(nums, mid + 1, right);\n        return root;\n    }\n};\n\n```\n# Code\n```python3 []\nfrom typing import List, Optional\n\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> Optional[\'TreeNode\']:\n        if not nums:\n            return None\n        mid = len(nums) // 2\n        root = TreeNode(nums[mid])\n        root.left = self.sortedArrayToBST(nums[:mid])\n        root.right = self.sortedArrayToBST(nums[mid + 1:])\n        return root\n\n```\n### Summary\nThis 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.\n\n![WhatsApp Image 2024-10-25 at 11.38.29.jpeg](https://assets.leetcode.com/users/images/a9ab9e2f-e893-4283-83af-8aa32ace8a3b_1729909241.2215364.jpeg)\n\n
['Array', 'Divide and Conquer', 'C++', 'Java', 'Python3']