Convert Sorted Array to Binary Search Tree
Easy · Trees · Array · Divide and Conquer · Tree · Binary Search Tree
Problem
Given an integer array nums sorted in strictly increasing order, build a height-balanced binary search tree that contains exactly its values and return its root.
Height-balanced means that at every node the heights of the left and right subtrees differ by at most one. Several trees usually qualify; any of them is accepted. Results are shown in level order, with None for a missing child.
Examples
Input: nums = [-4,-1,0,3,8,9,12] Output: [3,-1,9,-4,0,8,12]
Seven values fill three levels exactly, so the balanced tree is unique: 3 at the root, -1 and 9 below it, the rest as leaves.
Input: nums = [1,2,3,4,5] Output: [3,1,4,None,2,None,5]
Taking the left middle of every range gives this tree. Other balanced trees, such as [3,2,5,1,None,4], are accepted as well.
Input: nums = [7] Output: [7]
A single node.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in strictly increasing order
Approaches
- Middle element as root, by slicing — time O(n log n), space O(n)
Follow-up
With a sorted linked list there is no index access, so finding each middle costs a walk (O(n log n) overall). Building the tree in in-order instead, consuming the list from the front while recursing on sizes, brings it back to O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
