Convert Sorted Array to Binary Search Tree

Given a sorted (ascending) array, convert it into a height-balanced BST.

Function signature

func SortedArrayToBST(nums []int) *TreeNode

Inputs / outputs

• nums: sorted array of integers.
• Return: root of a height-balanced BST.

Example

nums = [-10,-3,0,5,9]
Output: a balanced BST with root 0

Constraints

• 0 <= len(nums) <= 100_000

Core idea (near-solution)

Choose the middle element as the root to keep the tree balanced, then recurse on left and right halves.

Invariant: each recursive call builds a BST from the subarray nums[lo:hi].

Algorithm (step-by-step)

1. If the subarray is empty, return nil.
2. Pick mid = (lo + hi) / 2 as the root.
3. Recursively build left subtree from lo..mid-1 and right subtree from mid+1..hi.
4. Return the root.

Correctness sketch

• Invariant: each recursive call builds a BST from the subarray nums[lo:hi].
• The problem is split into independent subproblems.
• By induction, recursive solutions are correct.
• The combine step preserves correctness for the full problem.

Trace (hand walkthrough)

Example input:
nums = [-10,-3,0,5,9]
Output: a balanced BST with root 0

Walk:
- mid=0 -> root 0
- left [-10,-3] -> mid -3 (left child), right [5,9] -> mid 5 (right child)
- remaining nodes -10 and 9 become leaves

Pitfalls to avoid

• Using an endpoint instead of the middle (creates skewed trees).
• Off-by-one errors when splitting subarrays.

Complexity

• Time: O(n).
• Extra space: O(log n) recursion depth for a balanced tree.

Implementation notes (Go)

• Use indices instead of slicing to avoid extra allocations.