Convert Sorted Array to Balanced BST in DSA C - Execution Trace

Concept Flow - Convert Sorted Array to Balanced BST

Start with sorted array

↓

Find middle element

→Create root node with middle

↓

Left subarray

→Recursively build left subtree

↓

Right subarray

→Recursively build right subtree

↓

Attach left and right subtrees to root

↓

Return root of balanced BST

We pick the middle element as root, then recursively build left and right subtrees from left and right halves of the array.

Execution Sample

DSA C

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

This code builds a balanced BST from a sorted array by choosing the middle element as root and recursively building left and right subtrees.

Execution Table

Step	Operation	Subarray Range	Node Created	Pointer Changes	Visual State
1	Find middle of [1,2,3,4,5,6,7]	0-6	Node(4)	root = Node(4)	4 / \
2	Build left subtree from [1,2,3]	0-2	Node(2)	root->left = Node(2)	4 / \ 2 -
3	Build left subtree of Node(2) from [1]	0-0	Node(1)	Node(2)->left = Node(1)	4 / \ 2 - / 1
4	Build right subtree of Node(2) from [3]	2-2	Node(3)	Node(2)->right = Node(3)	4 / \ 2 - / \ 1 3
5	Build right subtree from [5,6,7]	4-6	Node(6)	root->right = Node(6)	4 / \ 2 6 / \ - 1 3 -
6	Build left subtree of Node(6) from [5]	4-4	Node(5)	Node(6)->left = Node(5)	4 / \ 2 6 / \ / 1 3 5 -
7	Build right subtree of Node(6) from [7]	6-6	Node(7)	Node(6)->right = Node(7)	4 / \ 2 6 / \ / \ 1 3 5 7
8	Return root	0-6	-	-	Balanced BST complete

💡 All subarrays processed, recursion ends when start > end

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
start	0	0	0	0	0	4	4	6	N/A
end	6	6	2	0	2	6	4	6	N/A
mid	N/A	3	1	0	2	5	4	6	N/A
root	NULL	Node(4)	Node(2)	Node(1)	Node(3)	Node(6)	Node(5)	Node(7)	Node(4)
root->left	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Node(2)
root->right	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Node(6)

Key Moments - 3 Insights

Why do we choose the middle element as the root?

Choosing the middle element (see Step 1 in execution_table) ensures the tree is balanced because it splits the array into two halves of nearly equal size.

What happens when the subarray is empty?

When start > end (exit condition), the function returns NULL (Step 8), meaning no node is created for that subtree.

How do left and right subtrees get attached to the root?

After creating the root node, recursive calls build left and right subtrees, and their returned nodes are assigned to root->left and root->right respectively (Steps 2-7).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which node is created and attached?

A Node(3) attached as right child of Node(2)

B Node(5) attached as left child of Node(6)

C Node(1) attached as left child of Node(2)

D Node(7) attached as right child of Node(6)

💡 Hint

Check Step 3 in execution_table under 'Node Created' and 'Pointer Changes'

At which step does the recursion start building the right subtree of the root?

A Step 5

B Step 2

C Step 7

D Step 4

💡 Hint

Look at 'Operation' and 'Pointer Changes' columns in execution_table

If the array had only one element, what would the function return?

A NULL

B A node with that element and no children

C A node with that element and one child

D An empty tree

💡 Hint

Refer to the base case in the code and the exit condition in execution_table

Concept Snapshot

Convert Sorted Array to Balanced BST:
- Pick middle element as root
- Recursively build left subtree from left half
- Recursively build right subtree from right half
- Base case: start > end returns NULL
- Result is a balanced BST with minimal height

Full Transcript

This concept converts a sorted array into a balanced binary search tree by choosing the middle element as the root node. The process recursively builds left and right subtrees from the left and right halves of the array. The base case occurs when the subarray is empty, returning NULL. The execution table shows each step creating nodes and attaching them to form the balanced BST. Key moments clarify why the middle element is chosen and how recursion attaches subtrees. The visual quiz tests understanding of node creation and recursion steps.

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