Sorted Array to BST
Mahabharata — The Perfectly Balanced Formation — Build a Height-Balanced BST from Sorted Array
मध्य तत्व — root बनता है। बायाँ आधा — बायाँ वृक्ष; दायाँ आधा — दायाँ वृक्ष॥
*Middle element — becomes the root. Left half — left tree; right half — right tree.*
The Story
Convert a sorted integer array to a height-balanced BST.
For `nums=[-10,-3,0,5,9]`: a valid answer is `[0,-3,9,-10,null,5]` (BST with root=0).
**Binary search recursion:** - The middle element becomes the root (for height balance) - Elements to the left → left subtree - Elements to the right → right subtree
```java public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } TreeNode build(int[] nums, int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; // Prefer left-middle for ties TreeNode root = new TreeNode(nums[mid]); root.left = build(nums, lo, mid - 1); root.right = build(nums, mid + 1, hi); return root; } ```
Why is this height-balanced? At each step, we split the array as evenly as possible. Left half has ⌊n/2⌋ elements, right half has ⌊(n-1)/2⌋ or ⌊n/2⌋ elements. The height difference is at most 1.
Trace `[-10,-3,0,5,9]`: - mid=2: root=0. Left: [-10,-3]. Right: [5,9] - Left mid=0: root=-10. Left: []. Right: [-3]. - Right mid=1: root=-3. Both sides empty. - Right mid=3: root=5. Left: []. Right: [9]. - Right mid=4: root=9. - Tree: [0,-10,5,null,-3,null,9] (one valid answer)
The Same Recursive Approach
Always pick leftmost or rightmost element as root. Results in skewed BST. Still O(n) but not balanced.
TreeNode unbalancedBST(int[] nums, int lo, int hi) {
if (lo > hi) return null;
TreeNode root = new TreeNode(nums[lo]); // Always leftmost → right-skewed
root.right = unbalancedBST(nums, lo+1, hi);
return root;
}The Mid-Element Root Wisdom
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int lo, int hi) {
if (lo > hi) return null;
int mid = lo + (hi - lo) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, lo, mid - 1);
root.right = build(nums, mid + 1, hi);
return root;
}Step-by-Step Walkthrough
nums=[1]: lo=0,hi=0. mid=0. root=1. Left:lo=0,hi=-1→null. Right:lo=1,hi=0→null. Return [1]. ✅
Deep Insight
**Why mid = lo + (hi-lo)/2?** Avoids integer overflow compared to `(lo+hi)/2`. For very large lo and hi, `lo+hi` could overflow.
**Left-middle vs right-middle:** For even-length arrays, two valid middle choices exist: - Left-middle: `mid = (lo+hi)/2` → slightly left-heavy tree - Right-middle: `mid = (lo+hi+1)/2` → slightly right-heavy tree
Both produce valid height-balanced BSTs. LeetCode accepts either.
**Sorted list to BST (tr-35):** Can't use random access, so must find middle with slow/fast pointers. Same idea, different implementation.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Unbalanced version |
| Optimal | O(n) | O(n) | n nodes created; O(log n) call stack for balanced tree |
Pattern Recognition
✅ Sorted array to BST: pick middle as root ✅ mid = lo + (hi-lo)/2 ✅ Recurse on left half and right half ✅ Produces height-balanced BST **LeetCode Trigger Phrases:** → "convert sorted array to BST" → Build balanced BST from sorted input → Binary search recursion for tree construction
Rig Veda / Gita tradition
मध्ये वैश्यतनूर्विप्र शूद्रास्तस्यैव पादजाः।
From the middle body of the Cosmic Person emerged the merchant class; from His feet came the servant class.
Connection: Building a balanced BST from a sorted array places the middle element at the root — the central, most balanced position. Like the cosmic order where the middle represents balance and equilibrium, the BST construction algorithm derives its root from the center of the sorted array. Everything to the left and right is recursively organized in the same balanced way, creating a perfectly proportioned structure from ordered input.