Convert Sorted Array to Binary Search Tree

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

Why this is worth learning

The middle element balances the number of remaining keys on each side; sorted order simultaneously makes those two ranges valid left and right subtrees.

Before coding: one-minute experiment

For [-10,-3,0,5,9], why is 0 a natural root? Must a test demand the exact same root for every even-length input?

Function signature

func SortedArrayToBST(nums []int) *TreeNode

Inputs / outputs

• nums: strictly increasing integer slice (no duplicate keys).
• Return: root of a height-balanced BST.

Example

nums = [-10,-3,0,5,9]
One valid output: [0,-10,5,null,-3,null,9]

Constraints

• 0 <= len(nums) <= 10_000
• nums is strictly increasing; the input is read-only.

Core idea (near-solution)

Recursively choose the middle element of each range as the subtree root. Values left of the middle form the left subtree; values right of it form the right subtree.

Invariant: build(lo, hi) returns a balanced BST containing exactly nums[lo:hi+1].

Algorithm (step-by-step)

1. If the range is empty, return nil.
2. Choose mid = lo + (hi-lo)/2.
3. Create a node with nums[mid].
4. Recursively build the left subtree from lo..mid-1.
5. Recursively build the right subtree from mid+1..hi.
6. Return the node.

Correctness sketch

For an empty range return nil. Otherwise choose its middle key, recursively build the range before it as the left subtree and after it as the right subtree. With strictly increasing input, every left key is smaller and every right key larger, so induction gives BST ordering at every node. The two range sizes differ by at most one, and recursively applying the same split bounds their resulting heights within one, yielding a height-balanced tree. Each index becomes exactly one node, so inorder recovers the entire original array with no omissions or duplicates. The input is read-only.

Trace (hand walkthrough)

[-10,-3,0,5,9]
mid 0 -> root
left [-10,-3] -> choose -10 or -3 depending on mid policy
right [5,9] -> choose 5 or 9 depending on mid policy

Pitfalls to avoid

• Building a skewed tree by always choosing the first element.
• Slicing repeatedly and creating unnecessary arrays.
• Forgetting the empty range base case.

Debugging lens

Test all subtree height differences, not only the root. Ensure recursive ranges exclude the chosen midpoint. Clarify that strict BST ordering needs distinct keys; sorted with duplicates alone is insufficient.

Complexity

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

Implementation notes (Go)

• Pass index ranges instead of allocating sub-slices.

Contract precision

The BST uses strict ordering: every key in a left subtree is smaller than its root, and every key in a right subtree is larger. Distinct sorted input supplies this property. Either middle key is acceptable for an even-size range; the reference chooses the lower midpoint. Tests check contents and balance rather than one exact shape.

Reconstruction checkpoint

For [-10,-3,0,5,9], why is 0 a natural root? Must a test demand the exact same root for every even-length input?

Return to Divide & Conquer · Module quiz