Convert Sorted Array to Binary Search Tree
Problem Description
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Example 1:
Explanation: [0,-10,5,null,-3,null,9] is also accepted.
Example 2:
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
numsis sorted in a strictly increasing order.
Solve it on LeetCode
Approaches
1. Divide and Conquer
Intuition:
The problem requires us to convert a sorted array into a height-balanced binary search tree (BST). The key observation here is that for the BST to be height-balanced, the middle of the array should be selected as the root. This condition ensures that the heights of the subtrees do not vary by more than one. The left half of the array would then form the left subtree, and the right half would form the right subtree. This naturally suggests a recursive divide-and-conquer algorithm:
- Base Case: If the current subarray is empty, return
null. - Calculate the middle index of the current subarray.
- Create a root node using the middle element of the subarray.
- Recursively build the left and right subtrees using the left and right halves of the array, respectively.
Code:
- Time Complexity: O(n), where n is the number of elements in the array. Each element is processed exactly once to construct the tree.
- Space Complexity: O(log n), which is the space complexity due to the recursion stack in the worst case of a balanced binary tree (height is log n).
2. Recursive approach using Divide and Conquer
Intuition:
While the recursive approach is intuitive, using an iterative approach can help us manage large input sizes or environments where stack depth is limited. For an iterative solution, we can use a stack to simulate the recursive calls. The stack will store not only the array indices but also pointers to the parent nodes to connect the newly created nodes as either left or right children.
- Use a stack to maintain a tuple of (node, left, right) where
nodeis the parent node, andleft,rightare the current subarray bounds. - Pop from the stack and use the middle of the current subarray to create a new TreeNode.
- Attach this new TreeNode to its parent node based on the side it was derived from (left or right).
- Push the bounds of the left and right subarrays along with references to the current TreeNode onto the stack.
Code:
- Time Complexity: O(n), as we process each element of the array exactly once.
- Space Complexity: O(n), because the space used by the stack could be proportional to the number of elements in the worst case.