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

Convert Sorted Array to Balanced BST

📖 Scenario: You are building a program to convert a sorted array of numbers into a balanced Binary Search Tree (BST). This is useful in many applications like searching and sorting where balanced trees give faster results.

🎯 Goal: Build a C program that takes a sorted array and creates a balanced BST from it. Then print the BST nodes in inorder traversal to verify the tree structure.

📋 What You'll Learn

Create a sorted integer array called arr with the exact values: {1, 2, 3, 4, 5, 6, 7}

Create a struct called Node with int data, Node* left, and Node* right

Write a function Node* sortedArrayToBST(int arr[], int start, int end) that builds a balanced BST from the array

Write a function void inorderTraversal(Node* root) that prints the BST nodes in inorder

Print the inorder traversal of the BST after building it

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding tree data structures and recursion is essential for software engineering roles involving algorithms, system design, and performance optimization.

1

Create the sorted array and Node struct

Create a sorted integer array called arr with these exact values: {1, 2, 3, 4, 5, 6, 7}. Also define a struct called Node with three members: int data, Node* left, and Node* right.

DSA C

# Create the sorted array and Node struct
// Your code here

Hint

Define the array with the exact values. Use typedef struct Node to create the Node structure with data, left, and right pointers.

2

Write the function to convert sorted array to balanced BST

Write a function called Node* sortedArrayToBST(int arr[], int start, int end) that creates a balanced BST from the sorted array. It should find the middle element as root, recursively build left subtree from left half, and right subtree from right half.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int arr[] = {1, 2, 3, 4, 5, 6, 7};

// Write the sortedArrayToBST function below
// Your code here

Hint

Use recursion. Base case: if start > end, return NULL. Find middle index, create a new node with middle value, then build left and right subtrees recursively.

3

Write inorder traversal function to print BST

Write a function called void inorderTraversal(Node* root) that prints the BST nodes in inorder (left, root, right) separated by spaces.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int arr[] = {1, 2, 3, 4, 5, 6, 7};

Node* sortedArrayToBST(int arr[], int start, int end) {
    if (start > end) {
        return NULL;
    }
    int mid = (start + end) / 2;
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = arr[mid];
    root->left = sortedArrayToBST(arr, start, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, end);
    return root;
}

// Write inorderTraversal function below
// Your code here

Hint

Use recursion. If root is NULL, return. Otherwise, print left subtree, then root data, then right subtree.

4

Build BST and print inorder traversal

In the main function, create a BST by calling sortedArrayToBST(arr, 0, 6) and store the result in a variable called root. Then print the inorder traversal of the BST by calling inorderTraversal(root). Finally, print a newline.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int arr[] = {1, 2, 3, 4, 5, 6, 7};

Node* sortedArrayToBST(int arr[], int start, int end) {
    if (start > end) {
        return NULL;
    }
    int mid = (start + end) / 2;
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = arr[mid];
    root->left = sortedArrayToBST(arr, start, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, end);
    return root;
}

void inorderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    // Build BST and print inorder traversal
    Node* root = NULL;
    // Your code here
    return 0;
}

Hint

Call sortedArrayToBST(arr, 0, 6) and save to root. Then call inorderTraversal(root) to print the nodes. Add a newline after printing.

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