#108

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Convert Sorted Array to Binary Search Tree

Pick the middle element as root at each step so the sorted array becomes a height-balanced BST with valid ordering.

array divide and conquer tree binary search tree binary tree

Problem Statement

You are given a strictly increasing integer array and need to turn it into a height-balanced binary search tree. The tree must keep BST ordering, so every value in the left subtree stays smaller than the root and every value in the right subtree stays larger. Because the input is already sorted, the real challenge is deciding which element becomes each subtree root.

A valid answer is not unique, but it must remain balanced enough that the depths of subtrees differ by at most one at each node. For nums = [-10,-3,0,5,9], choosing 0 first naturally splits the array into two nearly equal halves, which leads to outputs like [0,-3,9,-10,null,5]. With nums = [1,3], either 1 or 3 can be the root and still produce a height-balanced BST.

Examples

Example 1

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

Output: [0,-3,9,-10,null,5]

[0,-10,5,null,-3,null,9] is also accepted:

Example 2

Input: nums = [1,3]

Output: [3,1]

[1,null,3] and [3,1] are both height-balanced BSTs.

Constraints

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

Solution Approach

Recursive midpoint split with index bounds

The cleanest solution keeps two pointers, left and right, and recursively builds a subtree from nums[left:right]. Pick mid = (left + right) // 2, create a node from nums[mid], then recurse on left..mid-1 for the left child and mid+1..right for the right child. This works because the sorted order already guarantees that everything left of mid belongs in the BST's left side and everything right of mid belongs in the right side. Using index bounds avoids copying subarrays and keeps the implementation tight.

Why midpoint choice enforces balance

This problem is not about searching the array; it is about assigning subtree roots so the final BST stays height-balanced. If you always choose the first or last element, the tree degenerates into a linked list, especially on long inputs. Choosing the middle element keeps the two recursive halves as even as possible, so subtree heights stay close. For even-length ranges, either middle is acceptable, and both still satisfy the balance requirement. The important part is staying consistent with your split and recursing on the correct remaining ranges.

Iterative construction with queued ranges

You can also build the tree iteratively by storing work items that contain a parent node reference, a left and right index, and whether the new node should attach as a left or right child. For each range, compute its midpoint, create the node, attach it, then push its left and right subranges. This avoids recursive function calls but keeps exactly the same midpoint logic. It is useful if you want explicit state tracking, though it is usually more verbose than recursion for this problem and easier to miswire during child attachment.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Although the provided time complexity says "Depends on the final approach" and the provided space complexity says "Depends on the final approach," the standard midpoint recursion visits each array element once, so it runs in O(n) time. Its extra space is O(log n) for the recursion stack when the tree stays balanced. If you slice arrays at every step instead of passing indices, the space cost grows because each recursive level allocates new subarrays.

What Interviewers Usually Probe

Do you see that choosing the middle element is what satisfies both BST ordering and height balance at the same time?
Can you explain why using left and right indices is safer here than repeatedly slicing the array into subarrays?
Will you handle even-length ranges consistently and show that either middle choice still produces a valid height-balanced BST?

Common Pitfalls or Variants

Common pitfalls

Using the first or last element as each root, which preserves BST order but creates a skewed tree instead of a height-balanced one.
Recursing on the wrong ranges, such as including mid in a child call again, which causes infinite recursion or duplicate nodes.
Building with array slices everywhere, which still works logically but quietly increases memory use and can hurt performance on large inputs.

Follow-up variants

Convert a sorted singly linked list to a height-balanced BST, where random access is gone and midpoint handling changes.
Build the BST iteratively from a sorted array using an explicit queue or stack of index ranges instead of recursion.
Given a sorted array, return any height-balanced BST but prefer the left middle or right middle consistently for even-length segments.

FAQ

What is the key idea in Convert Sorted Array to Binary Search Tree?

Choose the middle element of each sorted segment as the root of that segment. That single rule preserves BST ordering and keeps left and right subtree sizes close enough to maintain height balance.

Why does the midpoint guarantee a height-balanced BST?

Because the midpoint splits the sorted array into two nearly equal halves. Each recursive call repeats the same balanced split, so subtree heights differ by at most about one level instead of drifting into a long chain.

Can I use either middle element when the segment length is even?

Yes. For an even-length range, either the left middle or right middle creates a valid height-balanced BST. The output tree shape may differ, but both still satisfy the problem because the answer is not unique.

Why is passing indices better than slicing arrays here?

Index bounds keep the recursion focused on the original array without allocating new lists. That avoids extra copying, keeps the implementation closer to O(log n) auxiliary space, and reduces off-by-one mistakes once ranges get small.

Is binary-tree traversal and state tracking the real pattern for this problem?

The stronger core pattern is divide and conquer on sorted ranges, with state tracking limited to the current left and right bounds. Traversal matters less than choosing the correct midpoint and preserving exact child ranges at each step.

terminal

Solution

Solution 1: Binary Search + Recursion

We design a recursive function $\textit{dfs}(l, r)$, which represents that the values of the nodes to be constructed in the current binary search tree are within the index range $[l, r]$ of the array $\textit{nums}$. This function returns the root node of the constructed binary search tree.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(l: int, r: int) -> Optional[TreeNode]:
            if l > r:
                return None
            mid = (l + r) >> 1
            return TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r))

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

Continue Practicing

#109 convert sorted list to binary search tree #106 construct binary tree from inorder and postorder traversal #105 construct binary tree from preorder and inorder traversal