**Explanation**

The point to this question is to use a **Divide and Conquer** approach when constructing a balanced BST. We define helper function *recurse(...)* that will split our subarray, from index *lo* to *hi*, into more or less 2 equal parts, if possible, since this will produce a balanced BST for us.

Cases to Consider:

- If
*lo == hi*, then we're creating a leaf node with value*nums[lo]*. We still need to recursively call*recurse(...)*on its left and right children to set them to*null*. - If
*lo > hi*, then we're returning*null*for a parent node. - If
*lo < hi*, then we're splitting the*nums*subarray from indices*lo*to*hi*in half, and we're recursively creating subtrees from them.

**Time Complexity**

The time complexity is O(n) where n is the size of *nums*, since our recurrence relation is T(n) = 2T(n/2) + O(1), which is equal to O(n) by Master Theorem.

```
class Solution {
public TreeNode recurse(int[] nums, int lo, int hi) {
if (hi < lo) { return null; }
int mid = (lo + hi)/2;
// Create tree structure here
TreeNode root = new TreeNode(nums[mid]);
root.left = recurse(nums, lo, mid - 1);
root.right = recurse(nums, mid + 1, hi);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return recurse(nums, 0, nums.length - 1);
}
}
```