Convert Sorted Array to Balanced BST in DSA C++

Mental Model

We pick the middle element of the sorted array as the root to keep the tree balanced. Then we do the same for left and right parts to build left and right subtrees.

Analogy: Imagine you have a sorted list of books on a shelf. To organize them into a balanced pyramid stack, you pick the middle book as the base center, then build left and right stacks from the halves, so the pyramid stays even on both sides.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Build a balanced binary search tree (BST) from the sorted array

Step 1: Pick middle element 4 as root

4 ↑ (root)
Left array: [1, 2, 3]
Right array: [5, 6, 7]

Why: Middle element keeps tree balanced by splitting array evenly

Step 2: Build left subtree from [1, 2, 3], pick 2 as left child

    4
   / 
  2 ↑
Left array: [1]
Right array: [3]

Why: Repeat middle element selection for left subtree

Step 3: Build left child of 2 from [1], pick 1

    4
   / 
  2
 / 
1 ↑

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3

    4
   / 
  2
 / \
1   3 ↑

Why: Single element becomes leaf node

Step 5: Build right subtree from [5, 6, 7], pick 6 as right child

    4
   / \
  2   6 ↑
 / \ 
1   3
Right array left: [5]
Right array right: [7]

Why: Repeat middle element selection for right subtree

Step 6: Build left child of 6 from [5], pick 5

    4
   / \
  2   6
 / \ / 
1  3 5 ↑

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7

    4
   / \
  2   6
 / \ / \
1  3 5  7 ↑

Why: Single element becomes leaf node

Result:

Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

TreeNode* sortedArrayToBSTHelper(const vector<int>& nums, int left, int right) {
    if (left > right) return nullptr; // base case: no elements

    int mid = left + (right - left) / 2; // find middle index
    TreeNode* root = new TreeNode(nums[mid]); // create root node with middle element

    root->left = sortedArrayToBSTHelper(nums, left, mid - 1); // build left subtree
    root->right = sortedArrayToBSTHelper(nums, mid + 1, right); // build right subtree

    return root; // return root of this subtree
}

TreeNode* sortedArrayToBST(const vector<int>& nums) {
    return sortedArrayToBSTHelper(nums, 0, (int)nums.size() - 1);
}

void printInOrder(TreeNode* root) {
    if (!root) return;
    printInOrder(root->left);
    cout << root->val << " ";
    printInOrder(root->right);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    TreeNode* root = sortedArrayToBST(nums);
    printInOrder(root);
    cout << "\n";
    return 0;
}

if (left > right) return nullptr; // base case: no elements

stop recursion when no elements left to process

int mid = left + (right - left) / 2; // find middle index

choose middle element to keep tree balanced

TreeNode* root = new TreeNode(nums[mid]); // create root node with middle element

create node with middle value

root->left = sortedArrayToBSTHelper(nums, left, mid - 1); // build left subtree

recursively build left subtree from left half

root->right = sortedArrayToBSTHelper(nums, mid + 1, right); // build right subtree

recursively build right subtree from right half

return root; // return root of this subtree

return constructed subtree root

Output

1 2 3 4 5 6 7 

Complexity Analysis

Time: O(n) because each element is visited once to create a node

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Compared to inserting elements one by one into BST (O(n log n)), this method builds balanced BST in linear time

Edge Cases

empty array

returns nullptr, no tree created

DSA C++

if (left > right) return nullptr; // base case: no elements

array with one element

creates single node tree

DSA C++

if (left > right) return nullptr; // base case: no elements

array with two elements

middle picks first element, second becomes right child

DSA C++

int mid = left + (right - left) / 2; // find middle index

When to Use This Pattern

When you see a sorted array and need a balanced BST, use the middle element as root and recursively build subtrees from halves to keep balance.

Common Mistakes

Mistake: Picking first or last element as root instead of middle
Fix: Always pick middle element to keep tree balanced

Mistake: Not handling base case when left > right causing infinite recursion
Fix: Add base case to return nullptr when no elements remain

Summary

Builds a balanced binary search tree from a sorted array by recursively choosing middle elements as roots.

Use when you want a height-balanced BST from sorted data for efficient search.

The key is picking the middle element to keep left and right subtrees balanced.

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