LeetCode 108 - Convert Sorted Array to Binary Search Tree

LeetCode Problem 108

Difficulty: 🟢 Easy
Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us a sorted integer array nums in strictly increasing order and asks us to convert it into a height-balanced binary search tree (BST).

A binary search tree is a binary tree where:

• Every node in the left subtree contains values smaller than the current node.
• Every node in the right subtree contains values larger than the current node.

A height-balanced tree means that for every node, the difference between the heights of its left and right subtrees is at most one. In practical terms, the tree should not become heavily skewed to one side, because a skewed tree behaves more like a linked list and loses the efficiency benefits of a BST.

The input is a sorted array, which is important because the sorted order naturally corresponds to an inorder traversal of a BST. Since inorder traversal of a BST produces values in sorted order, the challenge becomes reconstructing a balanced BST while preserving this ordering.

The expected output is the root node of a valid height-balanced BST. Importantly, the problem does not require a unique answer. Multiple valid balanced BSTs may exist for the same input. As long as the resulting tree satisfies both BST ordering and height-balance conditions, it is accepted.

The constraints tell us several important things:

• 1 <= nums.length <= 10^4 means the input size can be moderately large, so inefficient approaches should be avoided.
• nums is strictly increasing, meaning there are no duplicates. This simplifies BST construction because we never need to decide how to handle equal values.
• Values range from -10^4 to 10^4, but the magnitude of values is not especially important here. The structure of the array matters more than the numbers themselves.

Several edge cases deserve attention:

A single-element array such as [5] should produce a tree with just one node.

Arrays with two elements like [1,3] can form multiple valid balanced BSTs. The implementation must not assume only one correct shape exists.

Very small arrays are common sources of off-by-one errors when splitting into left and right halves.

Since the input is guaranteed to be sorted and non-empty, we do not need to validate sorting or handle empty input outside recursive base cases.

Approaches

Brute Force Approach

A brute-force idea would be to try constructing every possible BST from the given numbers and then check whether each tree is height-balanced.

Since the array is sorted, we could theoretically choose every element as a root, recursively generate all possible left and right subtrees, then validate whether the resulting tree is balanced and satisfies BST properties.

This approach is correct because it explores the entire solution space. Eventually, it would find at least one valid balanced BST.

However, this method is computationally infeasible. The number of possible BSTs grows exponentially, following the Catalan number sequence. Even for moderate input sizes, generating all possibilities becomes prohibitively expensive.

The brute-force method is therefore unsuitable for n = 10^4.

Optimal Approach, Divide and Conquer

The key insight is that a sorted array already contains the inorder traversal of a BST.

To keep the tree balanced, we should place the middle element of the array at the root. This naturally divides the remaining elements into two roughly equal halves:

• Elements to the left of the middle become the left subtree.
• Elements to the right become the right subtree.

Because the array is sorted:

• Left-side elements are always smaller than the root.
• Right-side elements are always larger than the root.

This automatically satisfies BST ordering.

We can recursively repeat the same process for each half of the array. Each recursive step reduces the problem size, producing a balanced structure.

This is a classic divide-and-conquer strategy.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Generates many BST possibilities and validates balance
Optimal	O(n)	O(log n)	Recursively selects midpoint to maintain balance

Algorithm Walkthrough

Optimal Algorithm

1. Define a recursive helper function that works on a subarray range using two indices, left and right.

Instead of slicing arrays repeatedly, we pass boundaries. This avoids unnecessary copying and keeps memory usage efficient. 2. Handle the base case.

If left > right, it means there are no elements remaining in this portion of the array. Return None (or nil in Go). 3. Compute the middle index.

Use:

mid = (left + right) // 2

The middle element is chosen because it produces the most balanced split possible. 4. Create a tree node using the middle element.

This node becomes the root of the current subtree. 5. Recursively construct the left subtree.

Call the helper on the left half:

left to mid - 1

Since all these values are smaller than the root, BST ordering remains valid. 6. Recursively construct the right subtree.

Call the helper on the right half:

mid + 1 to right

Since all these values are larger than the root, BST ordering is preserved. 7. Return the constructed node.

The recursion naturally assembles the full balanced BST from bottom to top.

Why it works

The algorithm works because each recursive call preserves two essential invariants:

First, BST ordering is maintained because the array is sorted. Choosing the middle element ensures all left-side values remain smaller and all right-side values remain larger.

Second, balance is maintained because each subtree receives approximately half of the remaining elements. Since recursive splits stay close in size, subtree heights differ by at most one, satisfying the height-balanced requirement.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

        def build_tree(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None

            mid = (left + right) // 2

            root = TreeNode(nums[mid])

            root.left = build_tree(left, mid - 1)
            root.right = build_tree(mid + 1, right)

            return root

        return build_tree(0, len(nums) - 1)

The implementation closely follows the divide-and-conquer strategy described earlier.

The nested helper function build_tree(left, right) recursively builds a subtree for a specific portion of the array. Using indices instead of array slicing avoids repeatedly allocating new lists, which improves efficiency.

The base case checks whether the current range is invalid (left > right). When this happens, there are no nodes to create, so None is returned.

The middle index is selected to maintain balance. A TreeNode is created with that value, then recursive calls build the left and right subtrees using the remaining halves of the array.

Finally, the recursion starts from the entire array range, 0 to len(nums) - 1.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {

	var buildTree func(left int, right int) *TreeNode

	buildTree = func(left int, right int) *TreeNode {
		if left > right {
			return nil
		}

		mid := (left + right) / 2

		root := &TreeNode{
			Val: nums[mid],
		}

		root.Left = buildTree(left, mid-1)
		root.Right = buildTree(mid+1, right)

		return root
	}

	return buildTree(0, len(nums)-1)
}

The Go implementation follows the same recursive structure as Python. Since Go does not support nested named functions directly, a function variable buildTree is declared and assigned an anonymous recursive function.

Go uses nil instead of None for empty child pointers. Tree nodes are allocated using struct pointers, such as &TreeNode{}.

Integer overflow is not a concern here because the array length is limited to 10^4, but in larger systems some developers prefer:

mid := left + (right-left)/2

to avoid overflow risks.

Go slices are reference-based, but we still avoid creating subslices repeatedly. Passing index boundaries is more memory-efficient.

Worked Examples

Example 1

Input:

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

Initial call:

build_tree(0, 4)

Step	Left	Right	Mid	Value Chosen	Result
1	0	4	2	0	Root node
2	0	1	0	-10	Left child of 0
3	1	1	1	-3	Right child of -10
4	3	4	3	5	Right child of 0
5	4	4	4	9	Right child of 5

Constructed tree:

        0
       / \
    -10   5
      \     \
      -3     9

This tree satisfies BST ordering and remains height-balanced.

Another valid answer is possible depending on midpoint selection.

Example 2

Input:

nums = [1, 3]

Initial call:

build_tree(0, 1)

Step	Left	Right	Mid	Value Chosen	Result
1	0	1	0	1	Root
2	1	1	1	3	Right child

Constructed tree:

    1
     \
      3

Another valid balanced tree is:

    3
   /
  1

Both are accepted because the problem allows multiple valid balanced BSTs.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every element becomes exactly one tree node
Space	O(log n)	Recursive call stack height in a balanced tree

The time complexity is O(n) because each array element is processed exactly once during node creation.

The space complexity is O(log n) due to recursion depth. Since the tree stays balanced, recursive calls split roughly in half each time, producing logarithmic stack usage. The tree itself is not counted as extra space because it is required output.

Test Cases

# Helper functions for testing
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def is_balanced(root):
    def height(node):
        if not node:
            return 0

        left_height = height(node.left)
        if left_height == -1:
            return -1

        right_height = height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return max(left_height, right_height) + 1

    return height(root) != -1

solution = Solution()

# Example 1
root = solution.sortedArrayToBST([-10, -3, 0, 5, 9])
assert inorder(root) == [-10, -3, 0, 5, 9]  # inorder must match sorted input
assert is_balanced(root)  # tree must be balanced

# Example 2
root = solution.sortedArrayToBST([1, 3])
assert inorder(root) == [1, 3]  # valid BST ordering
assert is_balanced(root)  # balanced tree

# Single element
root = solution.sortedArrayToBST([7])
assert inorder(root) == [7]  # one-node tree
assert is_balanced(root)

# Three elements
root = solution.sortedArrayToBST([1, 2, 3])
assert inorder(root) == [1, 2, 3]  # balanced middle root
assert is_balanced(root)

# Negative values
root = solution.sortedArrayToBST([-5, -2, -1])
assert inorder(root) == [-5, -2, -1]  # negative integers
assert is_balanced(root)

# Larger input
nums = list(range(100))
root = solution.sortedArrayToBST(nums)
assert inorder(root) == nums  # preserves sorted order
assert is_balanced(root)

# Boundary values
root = solution.sortedArrayToBST([-10000, 10000])
assert inorder(root) == [-10000, 10000]  # min/max constraints
assert is_balanced(root)

Test	Why
[-10,-3,0,5,9]	Validates official example and general recursion
[1,3]	Verifies handling of two-element arrays
[7]	Tests smallest valid input
[1,2,3]	Ensures midpoint balancing works
[-5,-2,-1]	Confirms negative values behave correctly
range(100)	Stress test for larger balanced recursion
[-10000,10000]	Tests constraint boundary values

Edge Cases

Single Element Array

An input like [5] is the smallest valid case. This can easily expose bugs where recursion does not terminate properly or child pointers are mishandled.

The implementation handles this correctly because left == right, so the middle index points to the single element. A node is created, and subsequent recursive calls immediately hit the left > right base case.

Two Element Array

Inputs such as [1,3] are tricky because there is no perfectly centered middle element. Different midpoint choices may create different but still valid balanced trees.

The implementation chooses one midpoint consistently using integer division. Whether 1 or 3 becomes the root, the resulting tree remains balanced and valid.

Large Input Size

The maximum input length can reach 10^4. A naive approach that repeatedly slices arrays could create unnecessary memory overhead.

This implementation avoids slicing entirely by passing index boundaries (left, right) into recursive calls. This ensures efficient memory usage and maintains O(n) runtime.

Negative Numbers and Wide Value Ranges

The array may contain negative values or very large positive values. Some implementations accidentally rely on assumptions about positivity.

This solution treats values purely as ordered integers. Since BST correctness depends only on relative ordering, negative numbers naturally work without any special handling.