EasyArrayDivide and ConquerTreeBinary Search TreeBinary Tree

Convert Sorted Array to Binary Search Tree

1 approach, code in every language

You are given an integer array nums that is sorted in strictly ascending order. Build and return a height-balanced binary search tree from these values.

A height-balanced tree is one in which, for every node, the heights of its two subtrees differ by at most one. Multiple valid trees may exist for the same input; any height-balanced BST is accepted.

Example 1

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

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

Choosing 0 (the middle element) as the root and recursing on the halves yields a balanced BST. Other balanced answers such as [0,-10,5,null,-3,null,9] are also valid.

Example 2

Input: nums = [1,3]

Output: [3,1]

With two elements, either 1 or 3 can serve as the root; both [3,1] and [1,null,3] are height-balanced.

Constraints

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

Divide and Conquer on the Middle

Take the middle value as the root so the two halves become balanced subtrees.

Loading animation…

Intuition

Because the array is already sorted, an in-order traversal of any BST built from it must reproduce the array. To keep the tree balanced we want roughly equal numbers of elements on both sides of each root, which is exactly what choosing the middle element accomplishes. The elements to the left of the middle form the left subtree and those to the right form the right subtree, and each half is solved with the same procedure. Recursion naturally handles arbitrarily deep splitting, and the base case is an empty range that produces a null child. Since each index becomes a node exactly once, the construction is linear.

Algorithm walkthrough

1Define a helper build(left, right) that constructs a BST from the inclusive index range.
2If left > right the range is empty, so return null.
3Compute mid = left + (right - left) / 2 to avoid overflow and pick a balanced pivot.
4Create a node holding nums[mid].
5Recursively build the left subtree from [left, mid - 1] and the right subtree from [mid + 1, right].
6Return the node; the initial call build(0, n - 1) returns the tree root.

Implementation

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            mid = left + (right - left) // 2
            node = TreeNode(nums[mid])
            node.left = build(left, mid - 1)
            node.right = build(mid + 1, right)
            return node

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

Time

O(n)

Space

O(log n)

Each array element yields exactly one node, so construction is linear. Because the split is always balanced, the recursion depth is O(log n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Balanced Marker Index is our own problem on the technique behind Convert Sorted Array to Binary Search Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free