Convert Sorted Array to Balanced BST in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index of the array segment.

DSA C++

int mid = start + (end - start) / [1];

Drag options to blanks, or click blank then click option'

A1

B3

C4

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using division by 3 or 4 instead of 2.

Forgetting to subtract start from end before dividing.

The middle index is found by dividing the length by 2 to split the array into two halves.

2fill in blank

medium

Complete the code to create a new tree node with the middle element as its value.

DSA C++

TreeNode* node = new TreeNode([1][mid]);

Drag options to blanks, or click blank then click option'

Alist

Bvector

Carr

Dtree

Attempts:

3 left

💡 Hint

Common Mistakes

Using an undefined variable name like 'list' or 'vector'.

Using 'tree' which is unrelated.

The array is named 'arr', so we access the middle element using arr[mid].

3fill in blank

hard

Fix the error in the recursive call to build the left subtree.

DSA C++

node->left = buildBST(arr, start, [1] - 1);

Drag options to blanks, or click blank then click option'

Amid

Bstart

Cend

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start or end incorrectly as the end index.

Using mid + 1 which belongs to the right subtree.

The left subtree includes elements before the middle, so end index is mid - 1.

4fill in blank

hard

Fill both blanks to build the right subtree correctly.

DSA C++

node->right = buildBST(arr, [1], [2]);

Drag options to blanks, or click blank then click option'

Amid + 1

Bstart

Cend

Dmid - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start or mid - 1 as start index for right subtree.

Swapping start and end indices.

The right subtree starts from mid + 1 to end of the array segment.

5fill in blank

hard

Fill all three blanks to complete the base case and recursive function call.

DSA C++

if (start > [1]) return nullptr;
int mid = start + (end - start) / [2];
TreeNode* node = new TreeNode(arr[mid]);
node->left = buildBST(arr, start, mid - 1);
node->right = buildBST(arr, mid + 1, [3]);
return node;

Drag options to blanks, or click blank then click option'

Aend

B2

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using start instead of end in base case.

Dividing by wrong number in mid calculation.

Using wrong end index for right subtree.

Base case checks if start is greater than end. Mid is calculated by dividing by 2. Right subtree ends at end.

Practice

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

easy

A. To create a BST with minimum height

B. To create a BST with maximum height

C. To create a BST with all nodes having two children

D. To create a BST with nodes in reverse order

Solution

1. Step 1: Understand the problem goal

   The goal is to convert a sorted array into a BST that is balanced, meaning the tree height is minimized.

2. Step 2: Reason about balanced BST

   A balanced BST has minimum height to ensure efficient search operations.

3. Final Answer:

   To create a BST with minimum height -> Option A

4. Quick Check:

   Balanced BST = Minimum height [OK]

Hint: Pick the option that minimizes tree height for balance [OK]

Common Mistakes:

• Thinking maximum height means balanced
• Assuming all nodes must have two children
• Confusing order of nodes with balance

2. Which of the following is the correct base case condition in the recursive function to convert a sorted array to a balanced BST?

easy

A. if (start > end) return nullptr;

B. if (start == end) return nullptr;

C. if (start < end) return nullptr;

D. if (start >= end) return nullptr;

Solution

1. Step 1: Identify base case for recursion

   The recursion should stop when the start index passes the end index, meaning no elements left.

2. Step 2: Match condition to code

   The condition if (start > end) return nullptr; correctly handles this base case.

3. Final Answer:

   if (start > end) return nullptr; -> Option A

4. Quick Check:

   Base case = start > end [OK]

Hint: Stop recursion when start index exceeds end index [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Using start < end which never stops recursion
• Using start >= end which excludes valid single element

3. Given the sorted array [2, 4, 6, 8, 10, 12, 14], which of the following is the correct inorder traversal of the balanced BST created by the standard conversion method?

easy

A. [6, 4, 2, 8, 10, 12, 14]

B. [8, 4, 2, 6, 12, 10, 14]

C. [2, 4, 6, 8, 10, 12, 14]

D. [14, 12, 10, 8, 6, 4, 2]

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal of a BST always returns the nodes in sorted order.

2. Step 2: Check given array and traversal

   The array is sorted. The balanced BST created from it will have inorder traversal same as the original array.

3. Final Answer:

   [2, 4, 6, 8, 10, 12, 14] -> Option C

4. Quick Check:

   Inorder traversal = sorted array [OK]

Hint: Inorder traversal of BST = sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming balanced BST changes inorder order
• Selecting reversed or mixed order arrays

4. What is the output BST preorder traversal for the sorted array [1, 2, 3, 4, 5] when converted to a balanced BST?

medium

A. [3, 2, 1, 5, 4]

B. [3, 1, 2, 4, 5]

C. [3, 2, 1, 4, 5]

D. [3, 1, 4, 2, 5]

Solution

1. Step 1: Build balanced BST from array

   Middle element is 3 (index 2), root node. Left subtree from [1,2], right subtree from [4,5].

2. Step 2: Construct preorder traversal

   Preorder = root, left subtree preorder, right subtree preorder.
   Left subtree indices [0,1], mid=(0+1)/2=0 root=1, right child from [1,1] root=2.
   Right subtree indices [3,4], mid=(3+4)/2=3 root=4, right child from [4,4] root=5.
   Preorder: 3, 1, 2, 4, 5.

3. Final Answer:

   [3, 1, 2, 4, 5] -> Option B

4. Quick Check:

   Preorder = root-left-right = [3,1,2,4,5] [OK]

Hint: Pick middle as root, preorder = root-left-right [OK]

Common Mistakes:

• Choosing wrong middle element for root
• Mixing preorder with inorder or postorder
• Incorrect subtree construction

5. Identify the error in this recursive function snippet for converting a sorted array to a balanced BST:

TreeNode* buildBST(int arr[], int start, int end) {
  if (start >= end) return nullptr;
  int mid = (start + end) / 2;
  TreeNode* root = new TreeNode(arr[mid]);
  root->left = buildBST(arr, start, mid - 1);
  root->right = buildBST(arr, mid + 1, end);
  return root;
}

medium

A. Right subtree call should use mid instead of mid + 1

B. Mid calculation should be mid = (start + end + 1) / 2

C. Left subtree call should use mid instead of mid - 1

D. Base case condition should be start > end, not start >= end

Solution

1. Step 1: Analyze base case condition

   The base case stops recursion when no elements remain. Using start >= end excludes the case when start == end, missing single element nodes.

2. Step 2: Correct base case for single element

   Base case should be start > end to allow processing single elements when start == end.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option D

4. Quick Check:

   Base case = start > end [OK]

Hint: Base case must allow single element processing [OK]

Common Mistakes:

• Using start >= end excludes valid nodes
• Changing mid calculation unnecessarily
• Incorrect subtree index ranges