BST from Sorted Array
What You'll Learn
You'll learn how to build a perfectly balanced binary search tree from a sorted array by recursively selecting middle elements as roots.
The Core Idea
When you have a sorted array, you have a golden opportunity to construct a balanced BST instead of a skewed one. The trick is simple: pick the middle element as your root, then recursively do the same for the left and right halves.
Why the middle? Because in a sorted array, the middle element naturally divides the data into two equal (or nearly equal) parts—everything to its left is smaller, everything to its right is larger. This satisfies the BST invariant while keeping the tree balanced.
The Process
Imagine you have [1, 3, 5, 7, 9, 11, 13]:
- Choose middle (7) as root
- Left subarray [1, 3, 5]: Choose middle (3) as left child
- Right subarray [9, 11, 13]: Choose middle (11) as right child
- Recursively continue until subarrays are empty
The recursion naturally creates a complete or nearly complete tree with minimal height.
Why This Matters
If you inserted these elements one-by-one in sorted order (1, 3, 5, 7...), you'd get a degenerate tree—essentially a linked list. But by choosing middle elements, you guarantee the height stays O(log n), making all BST operations efficient.
Think of it like organizing a tournament bracket: you don't put all strong players on one side. You distribute them evenly by choosing midpoints, creating balanced competition at every level.
Key Takeaway: Building a BST from a sorted array via recursive middle-element selection produces a balanced tree with optimal O(log n) height, maximizing search efficiency.