Convert Sorted Array to Balanced BST in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given a sorted array, a balanced BST is created by picking the middle element as root recursively. What is the inorder traversal output of the BST created from the array [1, 2, 3, 4, 5, 6, 7]?

DSA C

/*
Balanced BST from sorted array [1,2,3,4,5,6,7]:
          4
        /   \
       2     6
      / \   / \
     1   3 5   7
Inorder traversal prints nodes in ascending order.
*/

void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// Output of inorderTraversal(root) for the above tree?

A [7, 6, 5, 4, 3, 2, 1]

B [1, 2, 3, 4, 5, 6, 7]

C [4, 2, 1, 3, 6, 5, 7]

D [1, 3, 2, 5, 7, 6, 4]

💡 Hint

Inorder traversal of a BST always prints elements in sorted order.

The inorder traversal visits left subtree, root, then right subtree. For a BST, this prints nodes in ascending order.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

What is the height of a balanced BST created from a sorted array of 15 elements?

A 4

B 5

C 3

D 15

💡 Hint

Height of balanced BST is about log2(n+1) - 1.

A balanced BST built from a sorted array has height approximately log base 2 of (n+1) minus 1. For 15 elements, height = 4 (levels 0 to 4), so height is 4. Height is counted as edges, so height = levels - 1 = 4.

🔧 Debug

advanced

Identify the Bug in BST Construction Code

What error will this code produce when converting a sorted array to a balanced BST? ```c struct Node* sortedArrayToBST(int arr[], int start, int end) { if (start > end) return NULL; int mid = (start + end) / 2; struct Node* root = malloc(sizeof(struct Node)); root->data = arr[mid]; root->left = sortedArrayToBST(arr, start, mid - 1); root->right = sortedArrayToBST(arr, mid + 1, end); return root; } ``` Assume struct Node is defined correctly and malloc works.

A No error, code runs correctly and builds balanced BST

B Segmentation fault due to uninitialized root pointer

C Stack overflow due to infinite recursion

D Compilation error due to missing return type

💡 Hint

Check base case and recursive calls carefully.

The code correctly handles base case (start > end) and recursively builds left and right subtrees. It allocates memory properly and returns root. No errors expected.

❓ Predict Output

advanced

Output of Preorder Traversal of Balanced BST

What is the preorder traversal output of the balanced BST created from the sorted array [10, 20, 30, 40, 50, 60, 70]?

DSA C

/*
Balanced BST structure:
          40
        /    \
      20      60
     /  \    /  \
   10   30  50  70
Preorder traversal visits root, left, right.
*/

A [10, 20, 30, 40, 50, 60, 70]

B [20, 10, 30, 40, 60, 50, 70]

C [70, 60, 50, 40, 30, 20, 10]

D [40, 20, 10, 30, 60, 50, 70]

💡 Hint

Preorder traversal visits root first, then left subtree, then right subtree.

Starting at root 40, preorder visits 40, then left subtree (20, 10, 30), then right subtree (60, 50, 70).

🧠 Conceptual

expert

Minimum Number of Nodes for Height 3 Balanced BST

What is the minimum number of nodes in a balanced BST of height 3?

A 15

B 4

C 7

D 8

💡 Hint

Minimum nodes in height h balanced BST follow recurrence: N(h) = 1 + N(h-1) + N(h-2)

Minimum nodes for height 0 is 1, height 1 is 2, height 2 is 4, height 3 is 7 nodes.

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 create a BST with minimal height

C. To reverse the array elements

D. To sort the array again

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 for efficient operations.

2. Step 2: Identify balanced BST property

   A balanced BST has roughly equal nodes on left and right subtrees, minimizing height and ensuring faster search.

3. Final Answer:

   To create a BST with minimal height -> Option B

4. Quick Check:

   Balanced BST = minimal height [OK]

Hint: Balanced BST means minimal height tree from sorted array [OK]

Common Mistakes:

• Thinking the array needs to be reversed
• Confusing BST with linked list
• Ignoring the balance requirement

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 NULL;

B. if (start < end) return NULL;

C. if (start > end) return NULL;

D. if (start == 0) return NULL;

Solution

1. Step 1: Understand recursion base case

   When start index is greater than end index, it means no elements remain to process, so return NULL (no node).

2. Step 2: Check each option

   if (start > end) return NULL; correctly checks if start > end to stop recursion. Other options do not correctly represent the base case.

3. Final Answer:

   if (start > end) return NULL; -> Option C

4. Quick Check:

   Base case = start > end [OK]

Hint: Base case stops when start index passes end index [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning NULL too early
• Confusing start and end indices

3. Given the sorted array [1, 2, 3, 4, 5], what is the root value of the balanced BST created by the standard algorithm?

medium

A. 3

B. 1

C. 5

D. 4

Solution

1. Step 1: Find middle element of array

   The middle element of [1, 2, 3, 4, 5] is at index 2 (0-based), which is 3.

2. Step 2: Middle element becomes root

   In balanced BST from sorted array, middle element is root to balance left and right subtrees.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Middle element = root = 3 [OK]

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

Common Mistakes:

• Choosing first or last element as root
• Off-by-one error in middle index calculation
• Confusing array indices

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

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

medium

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

B. Mid calculation should be (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 should stop recursion when start > end, because when start == end, there is still one element to process.

2. Step 2: Check recursive calls

   Left subtree uses start to mid-1, right subtree uses mid+1 to end, which is correct.

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 excludes start == end to include single element nodes [OK]

Common Mistakes:

• Stopping recursion too early with start >= end
• Incorrect mid index calculation
• Wrong subtree index ranges

5. You have a sorted array [2, 4, 6, 8, 10, 12, 14]. After converting it to a balanced BST, what is the inorder traversal of the BST?

hard

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

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

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

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

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal of a BST always returns the sorted order of elements.

2. Step 2: Check given array and traversal

   The array is already sorted. After conversion to balanced BST, inorder traversal must return the same sorted array.

3. Final Answer:

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

4. Quick Check:

   Inorder traversal = sorted array [OK]

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Expecting different order after conversion
• Misunderstanding BST traversal properties