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.
This approach selects the middle element of the current array (or subarray) to ensure a balanced partitioning of elements, thus maintaining the height balance of the BST.
The middle element of the array becomes the root of the BST (or subtree), and the same operation is recursively applied to the left and right halves of the array to form the left and right subtrees respectively.
This C program defines a TreeNode structure and uses a helper function to recursively build the BST from the middle of the array. The recursive calls split the array into two halves to build the left and right subtrees.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.
Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.
| 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 |
Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 94,636 views views
Watch 9 more video solutions →Practice Convert Sorted Array to Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode