Course contentsShow
← Computer Science
Lesson 520 of 2,87212. Binary Search TreesFree lesson

BST from Sorted Array

Construct a balanced BST from a sorted array by recursively choosing middle elements as roots.

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]:

  1. Choose middle (7) as root
  2. Left subarray [1, 3, 5]: Choose middle (3) as left child
  3. Right subarray [9, 11, 13]: Choose middle (11) as right child
  4. 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.