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.The key idea in Convert Sorted Array to Binary Search Tree is to build a height-balanced BST from a sorted array. Since the array is already sorted, the middle element naturally becomes the root of the tree. This ensures that elements on the left are smaller and elements on the right are larger, satisfying the Binary Search Tree (BST) property.
Using a divide and conquer strategy works best here. Select the middle element as the root, recursively build the left subtree from the left half of the array, and the right subtree from the right half. This recursive splitting keeps the tree balanced and avoids skewed structures.
Because each element is processed once while constructing nodes, the algorithm is efficient. The recursion depth corresponds to the height of the balanced tree, making the approach both clean and optimal for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Divide and Conquer using middle element | O(n) | O(log n) recursion stack |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Choosing the middle element keeps the tree balanced because it splits the array into two nearly equal halves. This prevents the tree from becoming skewed and helps maintain logarithmic height, which is important for efficient operations.
Yes, this problem or similar variations are frequently asked in technical interviews at top companies. It tests understanding of recursion, divide and conquer techniques, and binary search tree properties.
The problem primarily uses a Binary Search Tree structure built from a sorted array. Recursion is commonly used to divide the array and create tree nodes while preserving the BST ordering property.
The optimal approach uses a divide-and-conquer strategy. Pick the middle element of the sorted array as the root and recursively construct the left and right subtrees from the remaining halves. This ensures the resulting tree is height-balanced and maintains BST properties.