Convert Sorted Array to Balanced BST in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal when converting a sorted array to a balanced BST?

To create a binary search tree where the height difference between left and right subtrees of any node is minimal, ensuring efficient search operations.

beginner

Why do we pick the middle element of the sorted array as the root in this conversion?

Choosing the middle element ensures that the left and right subtrees have roughly equal numbers of nodes, keeping the tree balanced.

intermediate

What is the time complexity of converting a sorted array to a balanced BST?

O(n), where n is the number of elements in the array, because each element is visited once to create nodes.

beginner

In the recursive approach, what are the base cases when converting a sorted array to a balanced BST?

When the start index is greater than the end index, it means there are no elements to process, so return null.

beginner

How does the recursive function build the left and right subtrees?

It recursively calls itself on the left half of the array for the left subtree and on the right half for the right subtree.

What element is chosen as the root when converting a sorted array to a balanced BST?

A The first element

B The last element

C The middle element

D A random element

The middle element is chosen to keep the tree balanced by evenly dividing the array.

What is the base case in the recursive function for this conversion?

A When the middle element is null

B When start index equals end index

C When the array is empty

D When start index is greater than end index

The recursion stops when the start index is greater than the end index, meaning no elements remain.

What is the time complexity of converting a sorted array to a balanced BST?

A O(n log n)

B O(n)

C O(n^2)

D O(log n)

Each element is processed once, so the time complexity is O(n).

Which traversal order is naturally followed when building the BST from the sorted array?

A Preorder

B Inorder

C Postorder

D Level order

The root is created first, then left and right subtrees, matching preorder traversal.

Why is the resulting BST balanced?

A Because the middle element is chosen as root at each step

B Because duplicates are removed

C Because the tree is built from left to right

D Because the array is sorted

Choosing the middle element as root ensures left and right subtrees are balanced.

Explain step-by-step how to convert a sorted array into a balanced BST using recursion.

Think about dividing the array and building nodes from the middle.

Describe why the balanced BST created from a sorted array is efficient for search operations.

Consider how balanced trees keep search times low.

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