How do you approach Convert Sorted Array to Balanced BST?

The middle element of a sorted range must be the root - that is what splits the remaining values evenly between the two subtrees.

What is the time complexity of Convert Sorted Array to Balanced BST?

Time complexity: O(n) - each element becomes a root exactly once.. Space complexity: O(log n) for the recursion, plus the output..

What are common mistakes on Convert Sorted Array to Balanced BST?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Convert Sorted Array to Balanced BST

EasyData Structures

Description

Given an integer array sorted in ascending order, build a height-balanced binary search tree from it and return its preorder traversal.

To make the answer unique: when a range has an even number of elements, choose the left of the two middle elements as the root.

Example 1

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

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

Example 2

Input: nums = [1,3]

Output: [1, 3]

Example 3

Input: nums = [1,2,3,4,5]

Output: [3, 1, 2, 4, 5]

Constraints

- 0 <= nums.length <= 10^4 - nums is sorted in strictly ascending order - For an even-sized range, pick the LEFT middle element as the root. - Return the preorder traversal (root, left, right).

Convert Sorted Array to Balanced BST: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

The middle element of a sorted range must be the root - that is what splits the remaining values evenly between the two subtrees.
Recurse on the left half and the right half of the range to build the subtrees.
Preorder means: emit the root, then everything from the left half, then everything from the right half.

The optimal approach

Show the approach: Divide and conquer on the sorted range

Balance is about subtree sizes, and a sorted array hands you the split point for free: choosing the middle element as the root puts exactly half the remaining values on each side, so the two subtrees differ in size by at most one. Recursing gives a tree of height O(log n) by construction - no rotations, no rebalancing.

The BST ordering is automatic too, since everything left of the midpoint is smaller and everything right is larger. That is the same invariant binary search exploits, used in the opposite direction.

Emitting preorder (root, then left, then right) makes the recursion and the output line up exactly: append the midpoint, then recurse left, then recurse right. Nothing needs to be assembled afterwards.

The reason the problem pins down the even-length tie-break is that any midpoint choice yields a valid balanced BST, so the answer would otherwise not be unique - a real issue for automated checking, and a good thing to clarify in an interview before writing code.

Time: O(n) - each element becomes a root exactly once.
Space: O(log n) for the recursion, plus the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.