🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThe goal is to convert a sorted array into a height-balanced binary search tree (BST). My first thought is to leverage the properties of a BST, where t
![image.png](https://assets.leetcode.com/users/images/585a0ffb-a9c8-4e67-8712-feef6c7f6c71_1737272546.393905.png)

---


![1000068541.png](https://assets.leetcode.com/users/images/9df2f331-a912-4818-a774-074f9b1ff0f9_1737273609.5151494.png)



---

## Intuition
The goal is to convert a sorted array into a height-balanced binary search tree (BST). My first thought is to leverage the properties of a BST, where the left subtree contains values less than the root and the right subtree contains values greater than the root. Since the array is sorted, the middle element can serve as the root of the tree, ensuring that both subtrees are also balanced.

## Approach
1. **Recursive Construction**:
   - Implement a helper function (`buildBST`) that takes the current subarray defined by its start and end indices.
   - If the start index exceeds the end index, return null (base case).
   - Calculate the middle index of the current subarray; this will be the root of the subtree.
   - Recursively build the left subtree using the left half of the array and the right subtree using the right half.
   - Return the constructed tree node.

2. **Initial Function**:
   - The main function (`sortedArrayToBST`) checks if the input array is empty; if so, it returns null.
   - It then calls `buildBST` with appropriate parameters to construct and return the BST.

## Complexity
- **Time complexity**: $$O(n)$$ where $$n$$ is the number of elements in the input array. Each element is processed once to create nodes in the BST.
- **Space complexity**: $$O(h)$$ where $$h$$ is the height of the tree. In a balanced BST constructed from a sorted array, $$h$$ would be $$O(\log n)$$. However, in an unbalanced scenario (e.g., when creating a skewed tree), it could reach up to $$O(n)$$.

### Code Examples

```cpp []
#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        return buildBST(nums, 0, nums.size() - 1);
    }

    TreeNode* buildBST(vector<int>& nums, int start, int end) {
        if (start > end) return nullptr;

        int mid = start + (end - start) / 2; // Avoid potential overflow
        TreeNode* root = new TreeNode(nums[mid]);

        root->left = buildBST(nums, start, mid - 1);
        root->right = buildBST(nums, mid + 1, end);

        return root;
    }
};
```

```java []
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int start, int end) {
        if (start > end) return null;

        int mid = start + (end - start) / 2; // Avoid potential overflow
        TreeNode root = new TreeNode(nums[mid]);

        root.left = buildBST(nums, start, mid - 1);
        root.right = buildBST(nums, mid + 1, end);

        return root;
    }
}
```

```javascript []
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    sortedArrayToBST(nums) {
        if (nums.length === 0) return null;
        return this.buildBST(nums, 0, nums.length - 1);
    }

    buildBST(nums, start, end) {
        if (start > end) return null;

        const mid = Math.floor((start + end) / 2); // Calculate middle index
        const root = new TreeNode(nums[mid]);

        root.left = this.buildBST(nums, start, mid - 1);
        root.right = this.buildBST(nums, mid + 1, end);

        return root;
    }
}
```

```python []
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        return self.buildBST(nums, 0, len(nums) - 1)

    def buildBST(self, nums: List[int], start: int, end: int) -> TreeNode:
        if start > end:
            return None

        mid = (start + end) // 2 # Calculate middle index
        root = TreeNode(nums[mid])

        root.left = self.buildBST(nums, start, mid - 1)
        root.right = self.buildBST(nums, mid + 1, end)

        return root
```

```dart []
class TreeNode {
  int val;
  TreeNode? left;
  TreeNode? right;
  TreeNode([this.val = 0, this.left, this.right]);
}

class Solution {
  TreeNode? sortedArrayToBST(List<int> nums) {
    if (nums.isEmpty) return null;
    return buildBST(nums, 0, nums.length - 1);
  }

  TreeNode? buildBST(List<int> nums, int start, int end) {
    if (start > end) return null;

    int mid = (start + end) ~/ 2; // Calculate middle index
    TreeNode root = TreeNode(nums[mid]);

    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);

    return root;
  }
}
```

---





![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}

['Divide and Conquer', 'Tree', 'Binary Search Tree', 'C', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']