Watch 10 video solutions for Convert Sorted Array to Binary Search Tree, a easy level problem involving Array, Divide and Conquer, Tree. This walkthrough by NeetCode has 94,636 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Example 1:
Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3] Output: [3,1] Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums is sorted in a strictly increasing order.Problem Overview: You get a sorted integer array in ascending order. The task is to convert it into a height-balanced Binary Search Tree (BST). A balanced BST keeps the depth difference between left and right subtrees minimal, which ensures efficient search operations.
Approach 1: Sequential BST Insertion (O(n log n) time, O(n) space)
Insert elements from the sorted array into a BST one by one using standard BST insertion rules. For each element, start at the root and traverse left or right until you find the correct position. Because the array is sorted, inserting sequentially tends to create a skewed tree if you always append larger values to the right. Average performance is O(n log n), but the worst case becomes O(n^2) if the tree degenerates into a linked list. This approach is rarely used in interviews because it ignores the structure provided by the sorted array.
Approach 2: Recursive Middle Element as Root (O(n) time, O(log n) space)
Use a divide and conquer strategy. Pick the middle element of the sorted array as the root node. This choice naturally keeps the tree balanced because the left half of the array becomes the left subtree and the right half becomes the right subtree. Recursively repeat the same process for both halves until the subarray becomes empty.
Each element is processed exactly once, so the total time complexity is O(n). The recursion stack depth is proportional to the tree height, which is O(log n) for a balanced tree. The result satisfies both Binary Search Tree ordering rules and balanced tree constraints.
This method works because a sorted array already represents the inorder traversal of a BST. Selecting the midpoint ensures roughly equal node distribution on both sides. The recursion constructs a balanced binary tree while maintaining the BST property.
Recommended for interviews: Interviewers expect the recursive middle-element approach. It demonstrates recognition of the sorted structure and proper use of divide-and-conquer. Mentioning the naive insertion method shows baseline understanding, but implementing the midpoint recursion shows stronger algorithmic thinking and leads to the optimal O(n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential BST Insertion | O(n log n) avg, O(n²) worst | O(n) | Basic approach when constructing a BST from arbitrary order data |
| Recursive Middle Element as Root | O(n) | O(log n) | Best choice when the array is sorted and a height-balanced BST is required |