Convert Sorted Array to Balanced BST in DSA C

Mental Model

Pick the middle element of the sorted array as the root to keep the tree balanced. Recursively do the same for left and right halves to build subtrees.

Analogy: Imagine dividing a sorted list of books evenly to put the middle book on a shelf first, then placing the left half of books on the left side and the right half on the right side, so the shelf stays balanced and easy to search.

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 from the sorted array

Step 1: Choose middle element 4 as root

4
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 middle 2 as left child

    4
   / 
  2
Left subarray left: [1]
Left subarray right: [3]

Why: Recursively pick middle to keep left subtree balanced

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

    4
   / 
  2
 / 
1

Why: Single element becomes leaf node

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

    4
   / 
  2
 / \
1   3

Why: Single element becomes leaf node

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

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

Why: Recursively pick middle to keep right subtree balanced

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

    4
   / \
  2   6
 / \ / 
1  3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], which is 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 <stdio.h>
#include <stdlib.h>

// Define tree node structure
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Recursive function to convert sorted array to balanced BST
Node* sortedArrayToBST(int* arr, int start, int end) {
    if (start > end) {
        return NULL; // base case: no elements
    }
    int mid = start + (end - start) / 2; // find middle index
    Node* root = newNode(arr[mid]); // middle element becomes root

    root->left = sortedArrayToBST(arr, start, mid - 1); // build left subtree
    root->right = sortedArrayToBST(arr, mid + 1, end); // build right subtree

    return root;
}

// Helper function to print BST inorder (should print sorted array)
void inorderPrint(Node* root) {
    if (root == NULL) return;
    inorderPrint(root->left);
    printf("%d ", root->val);
    inorderPrint(root->right);
}

// Driver code
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    Node* root = sortedArrayToBST(arr, 0, n - 1);

    printf("Inorder traversal of constructed BST: ");
    inorderPrint(root);
    printf("\n");

    return 0;
}

int mid = start + (end - start) / 2; // find middle index

Calculate middle index to pick root for balanced split

Node* root = newNode(arr[mid]); // middle element becomes root

Create root node with middle element

root->left = sortedArrayToBST(arr, start, mid - 1); // build left subtree

Recursively build left subtree from left half

root->right = sortedArrayToBST(arr, mid + 1, end); // build right subtree

Recursively build right subtree from right half

Output

Inorder traversal of constructed BST: 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: Naive approach inserting elements one by one into BST can be O(n^2) if unbalanced; this method guarantees balanced tree in O(n)

Edge Cases

empty array

returns NULL, no tree created

DSA C

if (start > end) { return NULL; }

array with one element

creates single node tree

DSA C

if (start > end) { return NULL; }

array with two elements

root is middle (first element), second element becomes right child

DSA C

int mid = start + (end - start) / 2;

When to Use This Pattern

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

Common Mistakes

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

Mistake: Not handling base case when start > end causing infinite recursion
Fix: Add base case to return NULL when start > end

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