Convert Sorted Array to Balanced BST in DSA C++ - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing sorted data. You want to organize this data into a balanced tree structure called a Binary Search Tree (BST). This tree helps you find numbers quickly, like a well-organized phone book.

🎯 Goal: Build a balanced BST from a sorted array of integers. You will create the array, set up helper variables, write the logic to build the tree, and finally print the tree in order.

📋 What You'll Learn

Create a sorted array called nums with the exact values: 1, 2, 3, 4, 5, 6, 7

Create a struct TreeNode with int val, TreeNode* left, and TreeNode* right

Write a function TreeNode* sortedArrayToBST(int left, int right) that builds the balanced BST using recursion

Print the BST values in-order using inorderTraversal(TreeNode* root) to verify the tree structure

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and search engines to quickly find data without scanning everything.

💼 Career

Understanding BSTs and recursion is important for software engineering roles involving data structures and algorithms.

1

Create the sorted array and TreeNode struct

Create a sorted array called nums with these exact values: 1, 2, 3, 4, 5, 6, 7. Also, define a struct called TreeNode with an integer val, and two pointers left and right initialized to nullptr.

DSA C++

// Create the sorted array nums and define TreeNode struct
// Your code here

Hint

Use vector nums = {1, 2, 3, 4, 5, 6, 7}; to create the array. Define TreeNode with val, left, and right members.

2

Add helper function declaration and variables

Declare a function TreeNode* sortedArrayToBST(int left, int right) that will build the BST from the array indices left to right. Also, declare a pointer root of type TreeNode* initialized to nullptr.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

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

// Declare the function sortedArrayToBST
// Declare TreeNode* root initialized to nullptr
// Your code here

Hint

Write the function declaration for sortedArrayToBST and create a TreeNode* pointer called root set to nullptr.

3

Implement the recursive function to build the BST

Implement the function TreeNode* sortedArrayToBST(int left, int right) that builds the balanced BST recursively. Use the middle element as root, recursively build left subtree from left to mid - 1, and right subtree from mid + 1 to right. Assign the result to root by calling this function with 0 and nums.size() - 1.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

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

TreeNode* sortedArrayToBST(int left, int right) {
    // Your code here
}

// Assign root by calling sortedArrayToBST with 0 and nums.size() - 1
// Your code here

Hint

Use recursion to pick the middle element as root, build left subtree from left to mid-1, and right subtree from mid+1 to right.

4

Print the BST in-order to verify

Write a function void inorderTraversal(TreeNode* root) that prints the BST values in ascending order by visiting left subtree, root, then right subtree. Then call inorderTraversal(root) to print the values.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

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

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

int main() {
    TreeNode* root = sortedArrayToBST(0, nums.size() - 1);
    
    // Define inorderTraversal function
    // Call inorderTraversal(root) to print values
    // Your code here
    return 0;
}

Hint

Use recursion to print left subtree, then root value, then right subtree. Call this function with root.

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