For a balanced tree, pick the middle element as root. This guarantees roughly equal elements on each side:
def sortedArrayToBST(nums):
def build(left, right):
if left > right:
return null
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = build(left, mid - 1)
node.right = build(mid + 1, right)
return node
return build(0, len(nums) - 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 visited once. Space: for recursion on balanced tree.
This technique also appears in building segment trees.