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 the sorted array [1, 2, 3, 4, 5, 6, 7], what is the inorder traversal output of the balanced BST created by the standard middle-element approach?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    TreeNode* root = sortedArrayToBST(nums, 0, nums.size() - 1);
    vector<int> result;
    inorder(root, result);
    for (int v : result) cout << v << " ";
    return 0;
}

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

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

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

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

💡 Hint

Inorder traversal of a BST always returns the sorted array.

The inorder traversal of a binary search tree visits nodes in ascending order. Since the tree is built from a sorted array, the inorder traversal returns the original sorted array.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

What is the height of a balanced BST created from a sorted array of size 15 using the middle-element approach?

A 3

B 5

C 4

D 6

💡 Hint

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

A balanced BST built from a sorted array has height approximately log2(n+1). For n=15, log2(16) = 4.

🔧 Debug

advanced

Identify the Bug in BST Construction

What error will this code produce when converting a sorted array to a balanced BST?

DSA C++

TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
    if (left >= right) return nullptr;
    int mid = (left + right) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}

A The function returns nullptr for single element arrays, causing missing nodes.

B The function causes infinite recursion due to wrong base case.

C The function throws out_of_range exception accessing nums[mid].

D The function compiles and runs correctly with no errors.

💡 Hint

Check the base case condition carefully.

The base case 'if (left >= right)' returns nullptr even when left == right, so single element subarrays never create nodes, causing missing nodes in the tree.

❓ Predict Output

advanced

Output of Level Order Traversal of Balanced BST

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

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        res.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return res;
}

int main() {
    vector<int> nums = {10, 20, 30, 40, 50, 60, 70};
    TreeNode* root = sortedArrayToBST(nums, 0, nums.size() - 1);
    vector<int> result = levelOrder(root);
    for (int v : result) cout << v << " ";
    return 0;
}

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

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

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

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

💡 Hint

Level order visits nodes level by level from root.

The middle element 40 becomes root, left subtree root 20, right subtree root 60, then their children in order.

🧠 Conceptual

expert

Minimum Number of Nodes for Height 5 Balanced BST

What is the minimum number of nodes in a balanced BST of height 5 created from a sorted array?

A 64

B 32

C 63

D 31

💡 Hint

Minimum nodes in height h balanced BST is 2^h - 1.

A perfectly balanced BST of height 5 has minimum nodes = 2^5 - 1 = 31.

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