Convert Sorted Array to Binary Search Tree

The key idea

A sorted array already encodes BST order: the middle element is the root, everything left of it is smaller (left subtree), everything right is larger (right subtree). Always picking the middle of each slice keeps the two sides within one element of each other, which is exactly what height-balanced means.

Problem

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is one in which the depth of the two subtrees of every node never differs by more than one. When more than one valid answer exists, you may return any of them.

Constraints

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

Examples

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

Input: nums = [1,3] Output: [3,1]

Complexity

Time: O(n) Space: O(log n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →