Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree is a easy trees & bst problem solved with the bst basics pattern.
The best approach, optimal (divide and conquer on index bounds), runs in O(n) time and O(log n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursion with copied halves up.
Problem
You are given an integer array nums sorted in strictly increasing order. Build a height-balanced binary search tree that contains exactly these values and return its root.
Height-balanced means that for every node, the heights of its left and right subtrees differ by at most one. Many trees satisfy this; any of them is accepted. Trees are shown in level order, with null for a missing child.
Examples
Example 1
- Input
nums = [-6, -2, 0, 4, 9]- Output
[0, -6, 4, null, -2, null, 9]- Why
- 0 is the middle value. Its left half [-6, -2] and right half [4, 9] become balanced subtrees. Other balanced shapes, like [0, -2, 9, -6, null, 4], are also accepted.
Example 2
- Input
nums = [5, 8]- Output
[5, null, 8]- Why
- Either value can be the root; [8, 5] is accepted too.
Example 3
- Input
nums = [7]- Output
[7]- Why
- A single value becomes a single node.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in strictly increasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursion with copied halves | O(n log n) | O(n log n) |
| Optimal (divide and conquer on index bounds) | O(n) | O(log n) |
1Recursion with copied halves
O(n log n)Each of the log n levels of recursion copies about n values in total.O(n log n)Copies along one root-to-leaf path add up to O(n), but all copies made over the run total O(n log n); the tree itself is O(n).Make the middle element the root. Copy the left half and the right half into new arrays and build each subtree from its copy the same way. Because every split is even, the heights of the two sides differ by at most one.
- If the array is empty, return null.
- Let mid = length / 2 and create a node with nums[mid].
- Build the left child from a copy of nums[0 .. mid - 1].
- Build the right child from a copy of nums[mid + 1 .. end].
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) return null;
int mid = nums.length / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
return root;
}
}class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return rootclass Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) return nullptr;
int mid = nums.size() / 2;
TreeNode* root = new TreeNode(nums[mid]);
vector<int> left(nums.begin(), nums.begin() + mid);
vector<int> right(nums.begin() + mid + 1, nums.end());
root->left = sortedArrayToBST(left);
root->right = sortedArrayToBST(right);
return root;
}
};function sortedArrayToBST(nums) {
if (nums.length === 0) return null;
const mid = Math.floor(nums.length / 2);
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
}2Optimal (divide and conquer on index bounds)
O(n)Every element becomes exactly one node and each call does O(1) work.O(log n)The recursion depth is the height of a balanced tree, about log n (the output tree itself is not counted).Same idea, but describe each half by its index range [lo, hi] instead of copying it. The middle index of the range becomes the node, [lo, mid - 1] builds its left subtree and [mid + 1, hi] its right subtree.
- Call build(0, n - 1).
- In build(lo, hi): if lo > hi return null.
- mid = lo + (hi - lo) / 2; node = new TreeNode(nums[mid]).
- node.left = build(lo, mid - 1); node.right = build(mid + 1, hi); return node.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi) {
if (lo > hi) return null;
int mid = lo + (hi - lo) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums, lo, mid - 1);
node.right = build(nums, mid + 1, hi);
return node;
}
}class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(lo: int, hi: int) -> Optional[TreeNode]:
if lo > hi:
return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(nums) - 1)class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, (int) nums.size() - 1);
}
private:
TreeNode* build(vector<int>& nums, int lo, int hi) {
if (lo > hi) return nullptr;
int mid = lo + (hi - lo) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = build(nums, lo, mid - 1);
node->right = build(nums, mid + 1, hi);
return node;
}
};function sortedArrayToBST(nums) {
const build = (lo, hi) => {
if (lo > hi) return null;
const mid = lo + Math.floor((hi - lo) / 2);
const node = new TreeNode(nums[mid]);
node.left = build(lo, mid - 1);
node.right = build(mid + 1, hi);
return node;
};
return build(0, nums.length - 1);
}Edge cases to test
- One element
- Two elements: either one may be the root
- Even length: the middle can be the left or the right of the two centre values
- All negative values
Hints
Hint 1
Which value should be the root so that both sides get almost the same number of nodes?
Hint 2
Once the root is the middle element, the left half and right half are the same problem again.
Hint 3
Pass index bounds instead of copying the halves.
FAQ
What is the best time complexity for Convert Sorted Array to Binary Search Tree?
Optimal (divide and conquer on index bounds) runs in O(n) time and O(log n) extra space. Every element becomes exactly one node and each call does O(1) work.
Which pattern does Convert Sorted Array to Binary Search Tree use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Convert Sorted Array to Binary Search Tree?
Yes. Recursion with copied halves takes O(n log n) time and O(n log n) space. Make the middle element the root.
Which edge cases should I test for Convert Sorted Array to Binary Search Tree?
One element; Two elements: either one may be the root; Even length: the middle can be the left or the right of the two centre values; All negative values.