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.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To reverse the array elements

B. To create a linked list from the array

C. To sort the array again

D. To create a BST with minimal height for efficient search

Solution

1. Step 1: Understand the BST property

   A BST stores values so that left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Importance of balance

   A balanced BST has minimal height, which makes searching faster compared to a skewed tree.

3. Final Answer:

   To create a BST with minimal height for efficient search -> Option D

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Balanced BST means minimal height for fast search [OK]

Common Mistakes:

• Thinking the goal is to reverse or sort the array again
• Confusing BST with linked list
• Ignoring the balance aspect

2. Which TypeScript function signature correctly represents a function that converts a sorted array of numbers to a balanced BST node?

easy

A. function sortedArrayToBST(nums: number[]): TreeNode | null

B. function sortedArrayToBST(nums: string): TreeNode

C. function sortedArrayToBST(nums: number): TreeNode[]

D. function sortedArrayToBST(nums: any): void

Solution

1. Step 1: Check parameter type

   The input is a sorted array of numbers, so parameter type should be number[].

2. Step 2: Check return type

   The function returns the root node of the BST or null if empty, so return type is TreeNode | null.

3. Final Answer:

   function sortedArrayToBST(nums: number[]): TreeNode | null -> Option A

4. Quick Check:

   Input array and BST root output match signature [OK]

Hint: Input is number array, output is TreeNode or null [OK]

Common Mistakes:

• Using wrong input type like string or number instead of array
• Returning array instead of TreeNode
• Using void return type incorrectly

3. Given the following TypeScript code snippet, what is the in-order traversal output of the BST created from the array [1, 2, 3]?

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 {
  if (!nums.length) return null;
  const mid = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
}

function inorder(root: TreeNode | null, res: number[] = []): number[] {
  if (root) {
    inorder(root.left, res);
    res.push(root.val);
    inorder(root.right, res);
  }
  return res;
}

const bstRoot = sortedArrayToBST([1, 2, 3]);
console.log(inorder(bstRoot));

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [3, 2, 1]

D. [2, 3, 1]

Solution

1. Step 1: Build BST from array [1, 2, 3]

   Middle element is 2, root = 2; left subtree from [1], right subtree from [3].

2. Step 2: Perform in-order traversal

   In-order visits left, root, right: left subtree [1], root 2, right subtree [3] -> [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   In-order traversal returns sorted array [OK]

Hint: In-order traversal of BST returns sorted array [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order traversal
• Misidentifying the middle element as root
• Incorrect slicing of array for subtrees

4. Identify the bug in the following TypeScript function that attempts to convert a sorted array to a balanced BST:

function sortedArrayToBST(nums: number[]): TreeNode | null {
  if (nums.length === 0) return null;
  const mid = Math.ceil(nums.length / 2);
  const root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
}

medium

A. Using slice with wrong parameters

B. Using Math.ceil causes incorrect middle index, should use Math.floor

C. Incorrect return type, should return array

D. Missing base case for empty array

Solution

1. Step 1: Analyze middle index calculation

   Using Math.ceil(nums.length / 2) can select an index beyond the middle, causing imbalance.

2. Step 2: Correct middle index usage

   Math.floor(nums.length / 2) correctly picks the middle element for balanced BST construction.

3. Final Answer:

   Using Math.ceil causes incorrect middle index, should use Math.floor -> Option B

4. Quick Check:

   Middle index must be floor for balanced BST [OK]

Hint: Use Math.floor for middle index to keep tree balanced [OK]

Common Mistakes:

• Using Math.ceil instead of Math.floor for middle index
• Ignoring base case for empty array
• Misusing slice parameters

5. You have a sorted array [-10, -3, 0, 5, 9]. After converting it to a balanced BST using the standard approach, what is the root node's value and the structure of the tree?

hard

A. Root: -3; Left subtree: [-10]; Right subtree: [0, 5, 9]

B. Root: 5; Left subtree: [-10, -3, 0]; Right subtree: [9]

C. Root: 0; Left subtree: [-10, -3]; Right subtree: [5, 9]

D. Root: 9; Left subtree: [-10, -3, 0, 5]; Right subtree: []

Solution

1. Step 1: Find middle element as root

   Array length is 5, middle index = floor(5/2) = 2, root = 0.

2. Step 2: Divide array into left and right subtrees

   Left subtree from elements before index 2: [-10, -3]; right subtree from elements after index 2: [5, 9].

3. Final Answer:

   Root: 0; Left subtree: [-10, -3]; Right subtree: [5, 9] -> Option C

4. Quick Check:

   Middle element 0 is root, left and right split correctly [OK]

Hint: Root is middle element; left and right are array halves [OK]

Common Mistakes:

• Choosing wrong middle index
• Mixing left and right subtree elements
• Ignoring zero-based indexing