Convert Sorted Array to Balanced BST in DSA Javascript

Mental Model

We build a tree by picking the middle element as root to keep it balanced. Then we do the same for left and right parts.

Analogy: Imagine dividing a sorted list of books into three piles: the middle book goes on top, left pile forms the left stack, right pile forms the right stack, so the stacks stay 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: Build 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 keeps tree balanced by dividing array evenly

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 left 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

    4
   / \
  2   6
 / \

Why: Recursively pick middle to keep right subtree balanced

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 Javascript

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

function sortedArrayToBST(nums) {
  if (nums.length === 0) return null; // base case: empty array

  const mid = Math.floor(nums.length / 2); // find middle index
  const root = new TreeNode(nums[mid]); // middle element becomes root

  root.left = sortedArrayToBST(nums.slice(0, mid)); // build left subtree
  root.right = sortedArrayToBST(nums.slice(mid + 1)); // build right subtree

  return root;
}

function printBST(root) {
  if (!root) return "null";
  const left = printBST(root.left);
  const right = printBST(root.right);
  return `${root.val} -> (${left}, ${right})`;
}

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

if (nums.length === 0) return null; // base case: empty array

stop recursion when no elements left

const mid = Math.floor(nums.length / 2); // find middle index

choose middle element to keep tree balanced

const root = new TreeNode(nums[mid]); // middle element becomes root

create node for middle element

root.left = sortedArrayToBST(nums.slice(0, mid)); // build left subtree

recursively build left subtree from left half

root.right = sortedArrayToBST(nums.slice(mid + 1)); // build right subtree

recursively build right subtree from right half

Output

4 -> (2 -> (1 -> (null, null), 3 -> (null, null)), 6 -> (5 -> (null, null), 7 -> (null, 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: Naive approach inserting elements one by one into BST is O(n log n), this method is faster and produces balanced tree

Edge Cases

empty array

returns null, no tree created

DSA Javascript

if (nums.length === 0) return null; // base case: empty array

array with one element

creates single node tree

DSA Javascript

if (nums.length === 0) return null; // base case: empty array

array with two elements

root is first middle, left or right subtree has one node

DSA Javascript

const mid = Math.floor(nums.length / 2); // find middle index

When to Use This Pattern

When you see a sorted array and need a balanced search tree, use the middle element as root and build subtrees recursively to keep balance.

Common Mistakes

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

Mistake: Not slicing array correctly for left and right subtrees
Fix: Use nums.slice(0, mid) for left and nums.slice(mid+1) for right

Summary

Builds a balanced binary search tree from a sorted array by choosing middle elements as roots.

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

The key insight is picking the middle element splits the array evenly, keeping the tree balanced.

Practice

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

easy

A. To create a linked list from the array

B. To reverse the array elements

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

D. To sort the array again

Solution

1. Step 1: Understand the problem goal

   The goal is to build a BST that is balanced, meaning the tree height is minimized for faster search operations.

2. Step 2: Recognize the importance of balance

   A balanced BST ensures operations like search, insert, and delete run efficiently, typically in O(log n) time.

3. Final Answer:

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

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Pick the option about balanced tree and efficient search [OK]

Common Mistakes:

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

2. Which of the following is the correct way to find the middle index of an array arr in JavaScript for building a balanced BST?

easy

A. const mid = Math.floor(arr.length / 2);

B. const mid = arr.length / 2;

C. const mid = Math.ceil(arr.length / 2);

D. const mid = arr.length - 1;

Solution

1. Step 1: Understand array indexing

   Array indices start at 0, so to get the middle index, we divide length by 2 and take the floor to get an integer index.

2. Step 2: Use Math.floor for integer index

   Using Math.floor(arr.length / 2) gives the correct middle index for both even and odd lengths.

3. Final Answer:

   const mid = Math.floor(arr.length / 2); -> Option A

4. Quick Check:

   Middle index = floor(length/2) [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Using division without floor, resulting in float index
• Using Math.ceil which may pick wrong middle
• Using last index instead of middle

3. What will be the root node value of the balanced BST created from the sorted array [1, 3, 5, 7, 9]?

medium

A. 3

B. 5

C. 7

D. 9

Solution

1. Step 1: Find the middle element of the array

   The array length is 5, middle index = floor(5/2) = 2, so middle element is arr[2] = 5.

2. Step 2: Middle element becomes root

   In balanced BST from sorted array, the middle element is chosen as root to keep tree balanced.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Middle element = root = 5 [OK]

Hint: Root is middle element of sorted array [OK]

Common Mistakes:

• Picking first or last element as root
• Using ceil instead of floor for middle index
• Confusing array index with value

4. Consider this code snippet to convert a sorted array to a balanced BST:

function sortedArrayToBST(arr) {
  if (!arr.length) return null;
  const mid = Math.floor(arr.length / 2);
  const root = { val: arr[mid], left: null, right: null };
  root.left = sortedArrayToBST(arr.slice(0, mid));
  root.right = sortedArrayToBST(arr.slice(mid));
  return root;
}

What is the bug in this code?

medium

A. The right subtree slice should start from mid + 1, not mid

B. The base case should check for arr === null instead of length

C. The mid index calculation is incorrect

D. The root node is not created properly

Solution

1. Step 1: Analyze the slicing for right subtree

   The right subtree should exclude the middle element already used as root, so slice should start from mid + 1.

2. Step 2: Identify the bug

   Using arr.slice(mid) includes the middle element again in the right subtree, causing duplicate nodes and incorrect tree.

3. Final Answer:

   The right subtree slice should start from mid + 1, not mid -> Option A

4. Quick Check:

   Right subtree slice = arr.slice(mid + 1) [OK]

Hint: Right subtree excludes middle element: slice from mid+1 [OK]

Common Mistakes:

• Including middle element in both subtrees
• Wrong base case condition
• Incorrect mid calculation

5. Given the sorted array [-10, -3, 0, 5, 9], what is the preorder traversal (root-left-right) of the balanced BST created by the standard algorithm?

hard

A. [0, -10, -3, 5, 9]

B. [-3, -10, 0, 5, 9]

C. [5, 0, -10, -3, 9]

D. [0, -3, -10, 9, 5]

Solution

1. Step 1: Build the balanced BST

   Middle index = Math.floor(5/2) = 2, root = 0. Left subarray [-10, -3], length=2, mid=Math.floor(2/2)=1, left child = -3 (left of -3: [-10] mid=0 value -10; right of -3: empty). Right subarray [5, 9], length=2, mid=1, right child = 9 (left of 9: [5]; right of 9: empty).

2. Step 2: Perform preorder traversal (root-left-right)

   0, then left subtree: -3 then -10, then right subtree: 9 then 5. Result: [0, -3, -10, 9, 5].

3. Final Answer:

   [0, -3, -10, 9, 5] -> Option D

4. Quick Check:

   Preorder = root-left-right = [0, -3, -10, 9, 5] [OK]

Hint: Preorder = root, then left subtree, then right subtree [OK]

Common Mistakes:

• Wrong middle element selection for subtrees
• Confusing preorder with inorder or postorder
• Incorrect subtree construction