Module 18 · Tree BFS, Binary Search Trees, and Tries

178. Sorted Array to Balanced BST

Interview · Download this solution · All solutions and shared helpers

Problem

Build a height-balanced strict BST from a strictly increasing integer list. Return newly allocated nodes and leave the list unchanged. Choose mid=(left+right)//2 on each half-open range, so even-sized ranges use their upper middle. Empty input returns None.

Examples

Example 1

tree_values(sorted_array_to_bst([1,2,3,4]))
=> [3, 2, 4, 1]

The upper-middle rule fixes a deterministic balanced shape.

Example 2

sorted_array_to_bst([])
=> None

An empty interval creates no node.

Example 3

tree_values(sorted_array_to_bst([7]))
=> [7]

Both child ranges are empty.

Reveal the worked solution and reasoning

Why this mechanism works

The middle value separates smaller values from larger ones and keeps the two child sizes within one. Recursing on index ranges avoids slicing copies. The call contract combines two properties: its inorder reproduces the assigned range, and its subtrees are height-balanced.

State and boundaries

build(left,right) constructs exactly nums[left:right]. The midpoint belongs to the current root and is excluded from both children.

Protocol

Return None when left==right.
Choose the midpoint.
Allocate its node.
Build [left,mid) as left child.
Build [mid+1,right) as right child.
Return the node.

Visualization

[1,2,3,4] -> mid index 2 -> root 3
left range [1,2] -> root 2 with left 1
right range [4] -> root 4

Python implementation

from structures import TreeNode, tree_values

def sorted_array_to_bst(nums):
    def build(left, right):
        if left == right:
            return None
        mid = (left + right) // 2
        return TreeNode(nums[mid], build(left, mid), build(mid + 1, right))
    return build(0, len(nums))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

tree_values(sorted_array_to_bst([1,2,3,4]))

L4 sorted_array_to_bst: def build(left, right):
nums=[1, 2, 3, 4]

L5 build: if left == right:
left=0; right=4; nums=[1, 2, 3, 4]

L7 build: mid = (left + right) // 2
left=0; right=4; nums=[1, 2, 3, 4]; mid=2

L5 build: if left == right:
left=0; right=2; nums=[1, 2, 3, 4]

L7 build: mid = (left + right) // 2
left=0; right=2; nums=[1, 2, 3, 4]; mid=1

L5 build: if left == right:
left=0; right=1; nums=[1, 2, 3, 4]

L7 build: mid = (left + right) // 2
left=0; right=1; nums=[1, 2, 3, 4]; mid=0

L5 build: if left == right:
left=0; right=0; nums=[1, 2, 3, 4]

... 2 intermediate state changes omitted ...

L5 build: if left == right:
left=3; right=4; nums=[1, 2, 3, 4]

L7 build: mid = (left + right) // 2
left=3; right=4; nums=[1, 2, 3, 4]; mid=3

L5 build: if left == right:
left=3; right=3; nums=[1, 2, 3, 4]

L5 build: if left == right:
left=4; right=4; nums=[1, 2, 3, 4]

Result: [3, 2, 4, 1]. The upper-middle rule fixes a deterministic balanced shape.

sorted_array_to_bst([])

L4 sorted_array_to_bst: def build(left, right):
nums=[]

L5 build: if left == right:
left=0; right=0; nums=[]

Result: None. An empty interval creates no node.

Why the solution is correct

Both child ranges are strictly ordered around the midpoint, so recursively valid child BSTs form a valid parent BST whose inorder reproduces the range. Repeated near-equal size splits give subtree heights differing by at most one. Each child range is smaller, establishing termination.

Time and space

O(n) time, O(n) new-node output and O(log(n+1)) recursive stack space.

Common mistakes

Including mid in a child repeats a value and can prevent progress. Slicing is unnecessary when the contract already identifies an index interval.

Reasoning card

State: build(left,right) constructs exactly nums[left:right]. The midpoint belongs to the current root and is excluded from both children.

Invariant: Inorder traversal of the returned tree reproduces the input.

Decision to rehearse: Split sorted input into smaller left/right ranges.

Finish: Return the node

Transfer exercise

Accept sorted duplicate values under an explicitly chosen BST duplicate policy. Does midpoint splitting still guarantee both that policy and balance?