Build a BST from a Sorted Array

Building a Balanced BST from Sorted Data

Given a sorted array, you can build a height-balanced BST by always choosing the middle element as the root. This divide-and-conquer approach guarantees the resulting tree has minimum height.

Algorithm

BUILD_BST(array, start, end):
  if start > end: return NULL
  mid = (start + end) / 2
  node = new Node(array[mid])
  node.left  = BUILD_BST(array, start, mid - 1)
  node.right = BUILD_BST(array, mid + 1, end)
  return node

Example

Input: [1, 2, 3, 4, 5, 6, 7]

Step 1: mid = 3 → root = 4
Step 2: left = BUILD([1,2,3]) → mid=1, root=2
Step 3: right = BUILD([5,6,7]) → mid=5, root=6

Result:
        4
       / \
      2   6
     / \ / \
    1  3 5  7

This is a perfect binary tree with height 3 — the minimum possible for 7 nodes.

Why the Middle Element?

Choosing the middle element ensures that roughly half the remaining elements go to the left subtree and half to the right. This equal distribution at every level is what creates a balanced tree. If you picked the first element instead, you would get a right-skewed tree (which is exactly what happens when inserting sorted data into a plain BST one by one).

Time and Space Complexity

• Time: O(n) — each element is visited once
• Space: O(log n) for the recursion stack, plus O(n) for the tree itself

Converting Sorted Linked List to BST

The same approach works with a sorted linked list, but finding the middle element takes O(n) instead of O(1). You can optimize this using a slow/fast pointer approach or by using an inorder simulation technique that builds the tree from left to right.

Handling Even-Length Arrays

When the array length is even, there are two valid middle elements. The convention is to pick either the left-middle (floor) or right-middle (ceil) — both produce valid balanced BSTs with the same height.