Easy and simple Approach | Beats 100%
Intuition\nWhen converting a sorted array into a balanced BST:\n- The middle element of the array becomes the root of the BST.\n- Elements to the left of the mi
## Intuition\nWhen converting a sorted array into a balanced BST:\n- The middle element of the array becomes the root of the BST.\n- Elements to the left of the middle element in the array will form the left subtree.\n- Elements to the right of the middle element will form the right subtree.\n\nThis approach ensures that the BST remains balanced, meaning the heights of the subtrees of any node differ by at most one.\n\n## Approach\nThe approach involves using a recursive function `BST`:\n1. If the `start` index is greater than the `end` index, return `null`, indicating an empty subtree.\n2. Calculate the middle index (`mid`) of the current segment of the array.\n3. Create a new `TreeNode` with the value from `nums[mid]`.\n4. Recursively set the `left` subtree of the current node using elements from `start` to `mid-1`.\n5. Recursively set the `right` subtree of the current node using elements from `mid+1` to `end`.\n6. Return the current node.\n\nThis recursive function constructs the BST by continuously dividing the array into halves until all elements are used.\n\n## Complexity\n- **Time complexity:** \\(O(n)\\), where \\(n\\) is the number of elements in the `nums` array. This is because each element in the array is processed exactly once.\n- **Space complexity:** \\(O(\\log n)\\) on average due to the recursion stack. This represents the space used by the recursive calls. In the worst case, the space complexity could be \\(O(n)\\) if the tree is highly unbalanced.\n\n## Code\n```java\n/**\n * Definition for a binary tree node.\n * public 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 BST(nums, 0, nums.length - 1);\n    }\n\n    TreeNode BST(int[] nums, int start, int end) {\n        if (start > end) {\n            return null;\n        }\n        int mid = start + (end - start) / 2;\n        TreeNode node = new TreeNode(nums[mid]);\n        node.left = BST(nums, start, mid - 1);\n        node.right = BST(nums, mid + 1, end);\n        return node;\n    }\n}\n```
['Java']