#108
Convert Sorted Array to Binary Search Tree
Easy Middle as root
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Turn a sorted array into a height-balanced BST.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: build a height-balanced BST from a sorted array.
Why this works: the middle value as root splits the rest evenly; repeat on both halves.
Example: [-10, -3, 0, 5, 9]
root 0, left from [-10, -3] → -3 (-10), right from [5, 9] → 9 (5)✦Hints open one at a time
The middle element should be the root so both sides have equal size.
Apply the same idea to the left half and right half.
↗Approach
build(lo, hi): mid = (lo + hi) / 2 becomes the node; left = build(lo, mid − 1), right = build(mid + 1, hi).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] a, int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) >>> 1;
TreeNode root = new TreeNode(a[mid]); // middle keeps it balanced
root.left = build(a, lo, mid - 1);
root.right = build(a, mid + 1, hi);
return root;
}
}!Common mistake
Inserting elements one by one in order — that builds a linked-list-shaped tree.
Complexity
- Time: O(n).
- Space: O(log n) recursion.
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon