Convert Sorted Array to Binary Search Tree

Choosing the first or last value as the root preserves sorted order, but it produces a one-sided chain. The key is to choose a root that splits the remaining values into two nearly equal ranges.

Read the output contract first

You receive a strictly increasing integer array. For example:

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

You must return a binary tree that satisfies two conditions:

1. Binary search tree ordering: every value in the left subtree is smaller than the node, and every value in the right subtree is larger.
2. Height balance: at every node, the heights of the left and right subtrees differ by at most one.

The input length is between 1 and 10^4, so the input is never empty under the stated contract. Still, handling an empty range inside the recursive helper is essential.

There can be more than one correct tree. For the input above, both of these choices are valid:

        0                 0
       / \               / \
    -10   9           -3    5
      \   /           /      \
      -3 5          -10       9

The exact serialized output is not the point. The ordering and balance conditions are.

Spot the midpoint divide-and-conquer pattern

The sorted array already gives us the BST ordering for free.

If we choose nums[mid] as a root:

• Every value before mid is smaller, so it can belong to the left subtree.
• Every value after mid is larger, so it can belong to the right subtree.

The remaining question is balance.

Choosing an endpoint creates a chain:

1
 \
  3
   \
    5
     \
      7

This is technically ordered, but its height grows with the number of values. The midpoint gives the opposite shape: it leaves roughly half the values on each side.

That same decision can be repeated for each half:

1. Choose the middle value of the current range.
2. Build the left subtree from the range before it.
3. Build the right subtree from the range after it.
4. Stop when the range is empty.

This is divide and conquer. We solve one range by splitting it into two smaller ranges.

The problem appears under a Two Pointers classification because the recursive state is represented by a pair of bounds, left and right. But these are not conventional pointers scanning toward each other. They describe the current subproblem. The core mechanism is midpoint divide and conquer.

Build the recursive state

Define a helper:

build(left, right)

Its responsibility is precise:

Construct the tree using the inclusive array range nums[left:right + 1], and return that subtree's root.

For example:

build(1, 3)

means: build a tree from indices 1, 2, and 3.

The recursive steps are:

mid = (left + right) // 2

Then:

• nums[mid] becomes the current root.
• The left child comes from [left, mid - 1].
• The right child comes from [mid + 1, right].

The base case is:

if left > right:
    return None

When left > right, there are no values in the range. That means the requested subtree is empty.

Using inclusive bounds makes the state easy to audit:

Current range: [left, right]
Root index:    mid
Left range:    [left, mid - 1]
Right range:   [mid + 1, right]

The ranges never overlap. They also cover every index in the current range: the midpoint becomes the root, and every other index belongs to exactly one child range.

Partition invariant: every index in the current range is assigned once—to the current root or to exactly one recursive descendant range.

That invariant prevents both skipped values and duplicate nodes.

Prove ordering and balance

A working example is useful, but an interview solution should explain why the method works for every valid input.

Binary search tree ordering

The input is strictly increasing.

For a call on [left, right], we choose nums[mid] as the root:

• Every index in [left, mid - 1] contains a value smaller than nums[mid].
• Every index in [mid + 1, right] contains a value larger than nums[mid].

By the same reasoning, each recursive call builds correctly ordered subtrees. Therefore, the entire result satisfies the BST property.

Height balance

The midpoint divides the current range into two parts whose sizes differ by at most one.

For example, a range with five elements splits into two elements on one side and two on the other. A range with four elements splits into one side with one element and the other with two, depending on which middle convention we use.

The same midpoint rule is applied recursively to both sides. Each node therefore receives subtrees built from nearly equal-sized ranges, which keeps their heights within one level of each other.

Choosing the lower middle is a valid convention:

mid = (left + right) // 2

For an even-length range, choosing the upper middle would also produce a valid balanced tree. It may produce a different shape, and that is allowed. The important thing is to choose one convention and use it consistently.

Coverage and uniqueness

At each call:

• mid is used exactly once as the current node.
• The left recursion can use only indices before mid.
• The right recursion can use only indices after mid.

The child ranges are disjoint, and together with mid they cover the parent range. So every input value becomes one tree node, with no omissions and no duplicates.

Dry-run the recursion

Use:

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

The initial range is [0, 4].

The resulting tree is:

        0
       / \
    -10   5
      \    \
      -3    9

Notice the empty ranges. After selecting -10 at index 0, its left range is [0, -1]. Since left > right, that call returns None.

That return value is how the tree gets missing children. There is no special case for a leaf node; a leaf is simply a node whose two recursive child calls both receive empty ranges.

For a two-element input such as [1, 3], the lower-middle convention selects index 0:

  1
   \
    3

Selecting index 1 instead would produce:

  3
 /
1

Both trees are height-balanced BSTs.

Implement the Python solution cleanly

Here is the standard Convert Sorted Array to Binary Search Tree Python solution using index bounds rather than slicing:

class Solution:
    def sortedArrayToBST(self, nums):
        def build(left, right):
            # No values remain in this range.
            if left > right:
                return None

            # Choose the lower middle as the subtree root.
            mid = (left + right) // 2

            node = TreeNode(nums[mid])

            # Values before mid are smaller than the root.
            node.left = build(left, mid - 1)

            # Values after mid are larger than the root.
            node.right = build(mid + 1, right)

            return node

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

The platform supplies the TreeNode definition. The important parts of the implementation are the bounds:

• left and right identify the current inclusive range.
• mid selects the root value.
• mid - 1 closes the left range.
• mid + 1 starts the right range.
• left > right represents an empty subtree.

The order of the assignments is not logically required for correctness, but creating the node first makes the construction easy to follow: choose the root, build its left child, build its right child, return the completed subtree.

Avoid writing a version that slices the array at every recursive call:

# Avoid this style for an interview solution.
left_values = nums[:mid]
right_values = nums[mid + 1:]

Slicing creates new lists and hides the central invariant: which original indices belong to the current subproblem. Passing bounds keeps the ownership of each index visible and avoids repeated copying.

Complexity and edge cases

Let n be the number of values.

Time complexity

Each input value is used to create exactly one tree node. Each recursive call does constant work besides its two child calls.

Therefore:

Time: O(n)

Auxiliary space complexity

The resulting tree contains n nodes, but that returned structure is the required output rather than temporary workspace.

Because the tree is built from balanced ranges, the recursion depth is O(log n). The call stack therefore uses:

Auxiliary space: O(log n)

If an interviewer asks for total memory including the returned tree, the tree itself requires O(n) space.

Edge cases to check

One element

[7]

The root is 7. Both child calls use empty ranges and return None.

Two elements

[1, 3]

Either value can be the root under the balance definition. The lower-middle convention makes 1 the root.

Negative values

[-8, -4, -1]

Nothing changes. The algorithm relies on relative ordering, not on values being positive.

Odd and even lengths

For an odd-length range, the midpoint is exact. For an even-length range, integer division selects the lower middle. Both cases produce valid partitions.

Largest stated input

The constraints allow up to 10^4 values. The balanced recursion keeps the call depth logarithmic rather than allowing it to grow to n.

Before submitting, inspect the four failure points that cause most bugs:

• The empty-range check must be left > right.
• The left range must end at mid - 1.
• The right range must start at mid + 1.
• Every input value must be used once—never skipped, duplicated, or reused as both a root and a descendant.

The transferable pattern

When sorted data must become an ordered structure with balanced subproblems, let the middle carry both jobs:

• sorted order tells you which values belong left and right;
• the midpoint keeps the two subproblems nearly equal;
• the recursive bounds carry the proof through the implementation.

My interview rule is simple: when the data is already ordered and the output must stay ordered, ask whether the middle can become the root of a smaller problem.

Then write down the range invariant before writing the recursion:

build(left, right) constructs exactly nums[left:right + 1].

If the empty-range case, disjoint child ranges, BST ordering, and balance condition all follow from that statement, the implementation is usually on solid ground.