The O(n) Club: Convert Sorted Array to BST – Arrays Deserve a Glow-Up Too

The O(n) Club: Convert Sorted Array to BST – Arrays Deserve a Glow-Up Too

⚡ TL;DR

You want a balanced BST from your nice, sorted array. The trick: pick the middle element for your root every time you split, recurse until you’ve used up all your numbers, and poof! No linked-list-shaped disasters. Java makes it chill—one helper, no drama:

// The bad (unbalanced):
TreeNode tree = null;
for (int n : nums) tree = insert(tree, n);
 // The glow-up:
TreeNode tree = sortedArrayToBST(nums, 0, nums.length - 1);

🧠 How Devs Usually Mess This Up

Insert everything in order, and your binary search “tree” becomes a binary search pancake—flat, floppy, and about as performant as dial-up. And let’s not even start on how many people mix up “balanced” (heights of left/right subtrees differ by ≤1) with “perfect” (all levels filled). Bonus round: off-by-one math that makes your BST lean left or right like the Tower of Pisa. Good times!

🔍 What’s Actually Going On

Picture your array as a conference guest list you don’t want rioting. You pick the middle guest as the VIP root, split groups left/right, and recursively repeat until everyone’s seated. Your BST is the chill, balanced party where even the introverts get equal air time. Recursion sets everyone in just the right spot, so lookups stay fast and nobody sulks in a far-off branch.

• BST is satisfied: Left kids < parent < right kids.
• Height-balance is safe: No subtree is more than one level taller than its sibling.

This is why databases and search engines still depend on you not mangling this code.

🛠️ PseudoCode

• Want sortedArrayToBST(nums, left, right) for bounds.
• If left > right: stop. The array slice is empty, so you’re done here.
• Set mid = left + (right - left) / 2 (for integer overflow prevention, and because math is picky).
• Create your TreeNode: value = nums[mid].
• root.left is everything to the left (left to mid - 1).
• root.right is everything to the right (mid + 1 to right).
• Return root like the boss you are.

💻 The Code

// TreeNode for reference
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public TreeNode sortedArrayToBST(int[] nums) {
    return helper(nums, 0, nums.length - 1);
}
 private TreeNode helper(int[] nums, int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Midpoint mischief: Calculate mid wrong, and your “balanced” BST will limp forever. Use left + (right - left) / 2, not just (left + right) / 2.
• Don’t slice arrays: Just use left/right indices—cutting and copying costs memory and makes your stack weep.
• Unbalanced build = slow search: Inserting in order is O(n) search speed. Recursion keeps you at O(log n) height and O(n) time.
• Space: Stack is just O(log n)—unless you’re inlining arrays, in which case it’s O(n). (Please don’t.)

🧠 Interviewer Brain-Tattoo

If you build a BST from left to right, the only thing balanced is your boredom. Pick the middle, trust the recursion, and let Java do the heavy lifting for once.