## Convert Sorted Array to Binary Search Tree

• Time:O(n)
• Space:O(\log n)

## C++

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

private:
TreeNode* build(const vector<int>& nums, int l, int r) {
if (l > r)
return nullptr;

const int m = (l + r) / 2;
return new TreeNode(nums[m],
build(nums, l, m - 1),
build(nums, m + 1, r));
}
};
``````

## JAVA

``````class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] nums, int l, int r) {
if (l > r)
return null;

final int m = (l + r) / 2;
return new TreeNode(nums[m],
build(nums, l, m - 1),
build(nums, m + 1, r));
}
}
``````

## Python

``````class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(l: int, r: int) -> Optional[TreeNode]:
if l > r:
return None

m = (l + r) // 2
return TreeNode(nums[m],
build(l, m - 1),
build(m + 1, r))

return build(0, len(nums) - 1)
``````