Convert Sorted Array to Balanced BST in DSA Typescript

Mental Model

We build a tree by picking the middle element as root so both sides are balanced.

Analogy: Imagine dividing a sorted list of books evenly on a shelf by picking the middle book first, then doing the same for left and right halves to keep the shelf balanced.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Dry Run Walkthrough

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

Goal: Create a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

4
Array split: left=[1,2,3], right=[5,6,7]

Why: Middle element balances left and right subtrees

Step 2: Build left subtree from [1,2,3], pick middle 2 as left child

    4
   /
  2
Array split left=[1], right=[3]

Why: Recursively pick middle to keep subtree balanced

Step 3: Build left child of 2 from [1], pick 1

    4
   /
  2
 /
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3

    4
   /
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5,6,7], pick middle 6 as right child of 4

    4
   / \
  2   6
 / \

Why: Middle element balances right subtree

Step 6: Build left child of 6 from [5], pick 5

    4
   / \
  2   6
 / \  /
1   3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7

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

Why: Single element becomes leaf node

Result:

Balanced BST:
      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function sortedArrayToBST(nums: number[]): TreeNode | null {
  function helper(left: number, right: number): TreeNode | null {
    if (left > right) return null; // base case: no elements

    const mid = Math.floor((left + right) / 2); // pick middle element
    const node = new TreeNode(nums[mid]); // create node with middle value

    node.left = helper(left, mid - 1); // build left subtree
    node.right = helper(mid + 1, right); // build right subtree

    return node; // return subtree root
  }

  return helper(0, nums.length - 1);
}

function printBST(root: TreeNode | null): void {
  if (!root) return;
  const left = root.left ? root.left.val : 'null';
  const right = root.right ? root.right.val : 'null';
  console.log(`${root.val} -> left: ${left}, right: ${right}`);
  printBST(root.left);
  printBST(root.right);
}

// Driver code
const nums = [1, 2, 3, 4, 5, 6, 7];
const bstRoot = sortedArrayToBST(nums);
printBST(bstRoot);

if (left > right) return null; // base case: no elements

stop recursion when no elements left to process

const mid = Math.floor((left + right) / 2); // pick middle element

choose middle index to keep tree balanced

const node = new TreeNode(nums[mid]); // create node with middle value

create tree node with middle element

node.left = helper(left, mid - 1); // build left subtree

recursively build left subtree from left half

node.right = helper(mid + 1, right); // build right subtree

recursively build right subtree from right half

return node; // return subtree root

return current subtree root to parent

Output

4 -> left: 2, right: 6

2 -> left: 1, right: 3

1 -> left: null, right: null

3 -> left: null, right: null

6 -> left: 5, right: 7

5 -> left: null, right: null

7 -> left: null, right: null

Complexity Analysis

Time: O(n) because each element is visited once to create a node

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Compared to inserting elements one by one into BST (O(n log n)), this method builds balanced BST in linear time

Edge Cases

empty array

returns null (empty tree)

DSA Typescript

if (left > right) return null; // base case: no elements

array with one element

creates single node tree

DSA Typescript

if (left > right) return null; // base case: no elements

array with two elements

root is middle (first element), second element becomes right child

DSA Typescript

const mid = Math.floor((left + right) / 2); // pick middle element

When to Use This Pattern

When you see a sorted array and need a balanced BST, use the middle element as root and recursively build left and right subtrees from halves.

Common Mistakes

Mistake: Picking first or last element as root instead of middle
Fix: Always pick the middle element to keep tree balanced

Mistake: Not handling base case when left > right causing infinite recursion
Fix: Add base case to return null when no elements remain

Summary

Converts a sorted array into a balanced binary search tree by recursively choosing middle elements as roots.

Use when you want a height-balanced BST from sorted data for efficient search.

The key is picking the middle element each time to keep left and right subtrees balanced.