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 receive a sorted integer array in ascending order and must convert it into a height-balanced Binary Search Tree (BST). The BST property must hold (left < root < right), and the tree height should remain balanced so that operations stay efficient.
Approach 1: Sequential BST Insertion (O(n log n) time, O(n) space)
A straightforward idea is to iterate through the sorted array and insert each value into a BST using standard BST insertion rules. Each insertion places smaller values on the left and larger values on the right. Because the array is already sorted, every new element becomes the right child of the previous node, producing a highly skewed tree that behaves like a linked list.
This approach technically constructs a valid BST, but it fails the height-balanced requirement. Time complexity becomes O(n log n) in the average case but degrades to O(n^2) when the tree becomes completely skewed. Space complexity is O(n) for storing nodes. It demonstrates BST construction basics but does not satisfy the problem constraints.
Approach 2: Recursive Middle Element as Root (O(n) time, O(log n) space)
The optimal strategy leverages the sorted property of the array. The key insight: the middle element naturally divides the array into two equal halves. Choosing the middle element as the root guarantees that the left subtree contains smaller values and the right subtree contains larger values, which preserves the BST property.
From there, recursively build the tree. Pick the middle index mid = (left + right) / 2, create a node with nums[mid], and recursively construct the left subtree from the subarray [left, mid-1] and the right subtree from [mid+1, right]. Each recursive call repeats the same logic until the subarray becomes empty.
This divide-and-conquer pattern ensures the tree remains balanced because each level splits the array roughly in half. Every element becomes a node exactly once, producing O(n) time complexity. The recursion stack depth equals the height of the balanced tree, which is O(log n) space.
This solution directly applies concepts from Divide and Conquer and builds a balanced structure using properties of a Binary Search Tree. The resulting structure is also a valid Binary Tree where subtree heights differ by at most one.
Recommended for interviews: The recursive middle-element approach is what interviewers expect. It shows you recognize how sorted data enables balanced partitioning. Mentioning the naive insertion approach demonstrates understanding of BST construction, but implementing the divide-and-conquer solution shows stronger algorithmic reasoning 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.
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.
We design a recursive function dfs(l, r), which represents that the values of the nodes to be constructed in the current binary search tree are within the index range [l, r] of the array nums. This function returns the root node of the constructed binary search tree.
The execution process of the function dfs(l, r) is as follows:
l > r, it means the current array is empty, so return null.l leq r, take the element at index mid = \lfloor \frac{l + r}{2} \rfloor of the array as the root node of the current binary search tree, where \lfloor x \rfloor denotes the floor function of x.mid - 1 of the array. The values of the nodes in the left subtree are within the index range [l, mid - 1] of the array.mid + 1 of the array. The values of the nodes in the right subtree are within the index range [mid + 1, r] of the array.The answer is the return value of the function dfs(0, n - 1).
The time complexity is O(n), and the space complexity is O(log n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Recursive Middle Element as Root | 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. |
| Binary Search + Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential BST Insertion | O(n log n) avg, O(n^2) worst | O(n) | Useful for demonstrating basic BST insertion but does not guarantee a balanced tree |
| Recursive Middle Element as Root | O(n) | O(log n) | Best choice when the input array is sorted and a height-balanced BST is required |
Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 111,579 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