How to Solve Convert Sorted Array to Binary Search Tree

Use divide and conquer: choose the middle value as the root, then build the left subtree from the left half and the right subtree from the right half. That midpoint choice is what keeps Convert Sorted Array to Binary Search Tree balanced instead of turning the BST into a skewed chain. The main failure mode is picking endpoints or slicing carelessly and losing either balance or index correctness.

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

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.

How GhostInterview Helps

• GhostInterview can screenshot or capture the current LeetCode input and example tree state so the midpoint split stays aligned with the actual nums range on screen.
• GhostInterview can map the answer path from midpoint selection to subtree construction and state the matching O(n) time and O(log n) stack complexity clearly.
• GhostInterview supports screen-share workflows and captured layers, so the array indices, chosen midpoints, and partial BST structure can stay visible while you solve.

Topic Pages

• Array
• Divide and Conquer
• Tree
• Binary Search Tree
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.