Convert Sorted Array to Binary Search Tree

Given an integer array sorted in ascending order, convert it into a height-balanced binary search tree.

This problem is not mainly about binary search trees. It is about learning how sorted order can become a balanced recursive structure.

Function signature

func SortedArrayToBST(nums []int) *TreeNode

Node definition

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Input

• nums: a sorted ascending array of integers.

Output

• Return the root of a height-balanced BST containing exactly the values from nums.

A height-balanced binary tree is one where, for every node, the heights of the left and right subtrees differ by at most one.

Examples

Example 1

nums = [-10, -3, 0, 5, 9]

One valid output:

        0
      /   \
   -10     5
      \     \
      -3     9

Another valid output may choose the upper middle at some ranges. The exact shape can vary, but the tree must be a balanced BST and its inorder traversal must equal the input.

Example 2

nums = []

Output:

nil

Example 3

nums = [1]

Output:

1

Constraints

• 0 <= len(nums) <= 100_000
• nums is sorted in ascending order.

Learning target

You should learn to define an inclusive array range contract:

build(lo, hi) returns a height-balanced BST containing exactly nums[lo..hi].

Once this contract is clear, the code becomes almost mechanical.

Core idea

The array is sorted. The middle element is the best root because it leaves roughly the same number of values on both sides.

nums[lo..mid-1]  -> left subtree
nums[mid]        -> root
nums[mid+1..hi]  -> right subtree

This split preserves the BST property because all values before mid are smaller than the root position and all values after mid are larger.

It also preserves balance because the left and right ranges differ in size by at most one.

Near-solution algorithm

build(lo, hi):
    if lo > hi:
        return nil

    mid = lo + (hi - lo) / 2

    root = new TreeNode(nums[mid])
    root.Left = build(lo, mid - 1)
    root.Right = build(mid + 1, hi)

    return root

Use indices rather than slicing. It keeps boundaries explicit and avoids accidental allocation or confusing subarray ownership.

Detailed walkthrough

Input:

[-10, -3, 0, 5, 9]

Initial call:

build(0, 4)

Middle index is 2, value 0.

root = 0
left range = 0..1
right range = 3..4

Left side:

build(0, 1)
mid = 0
root = -10
left range = 0..-1 => nil
right range = 1..1

Right child of -10:

build(1, 1)
mid = 1
root = -3

Right side of original root:

build(3, 4)
mid = 3
root = 5
right child = 9

Final tree is balanced and inorder traversal returns the original array.

Correctness sketch

We prove the recursive contract by induction on the range length.

If lo > hi, the range is empty, and returning nil is correct.

For a non-empty range, the algorithm selects nums[mid] as root. The left recursive call receives exactly the values before mid; the right recursive call receives exactly the values after mid. By the induction hypothesis, both calls return correct balanced BSTs for those ranges. Attaching them under nums[mid] preserves BST ordering. Since the midpoint splits the range into nearly equal sizes, the resulting tree is height-balanced.

Complexity

• Time: O(n) because each value becomes one tree node.
• Extra space: O(log n) recursion stack for a balanced tree.

Pitfalls

Pitfall 1: Testing only inorder traversal

A skewed tree can still have the correct inorder traversal. Good tests also verify height balance.

Pitfall 2: Reusing mid in a child range

Wrong:

root.Left = build(lo, mid)

This repeats the root value and can cause infinite recursion for one-element ranges.

Correct:

root.Left = build(lo, mid-1)

Pitfall 3: Choosing an endpoint as root

Choosing the first or last element preserves the BST property but creates a skewed tree.

Implementation notes for Go

Use:

mid := lo + (hi-lo)/2

Then allocate:

node := &TreeNode{Val: nums[mid]}

Do not mutate nums. The input array is only read.