Java O(n) Easy To Understand, Optimal Solution

• 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:

1. 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.
2. If lo > hi, then we're returning null for a parent node.
3. 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);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.