For a balanced tree, pick the middle element as root. This guarantees roughly equal elements on each side:
function sortedArrayToBST(nums):
function build(left, right):
if left > right:
return null
mid = floor((left + right) / 2)
node = TreeNode(nums[mid])
node.left = build(left, mid - 1)
node.right = build(mid + 1, right)
return node
return build(0, nums.length - 1)
You're using divide and conquer. The middle element becomes the root, left half becomes left subtree, right half becomes right subtree.
Time: . Each element is visited once.
Space: for recursion on balanced tree.
This technique also appears in building segment trees.