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.