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 node

↓

Balanced BST constructed

Split the sorted array by middle element to create root, then recursively build left and right subtrees from subarrays.

Execution Sample

DSA C++

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

Recursively picks middle element as root and builds left and right subtrees from subarrays.

Execution Table

Step	Operation	Subarray Range	Node Created	Pointer Changes	Visual State
1	Find middle of [0..6]	[0..6]	Node(4)	root = Node(4)	4
2	Build left subtree of 4	[0..2]	Node(2)	root->left = Node(2)	4 / 2
3	Build left subtree of 2	[0..0]	Node(1)	Node(2)->left = Node(1)	4 / 2 / 1
4	Build left subtree of 1	[0..-1]	None	Node(1)->left = nullptr	No change
5	Build right subtree of 1	[1..0]	None	Node(1)->right = nullptr	No change
6	Build right subtree of 2	[2..2]	Node(3)	Node(2)->right = Node(3)	4 / 2 / \ 1 3
7	Build left subtree of 3	[2..1]	None	Node(3)->left = nullptr	No change
8	Build right subtree of 3	[3..2]	None	Node(3)->right = nullptr	No change
9	Build right subtree of 4	[4..6]	Node(6)	root->right = Node(6)	4 / \ 2 6 / \
10	Build left subtree of 6	[4..4]	Node(5)	Node(6)->left = Node(5)	4 / \ 2 6 / \ / 1 3 5
11	Build left subtree of 5	[4..3]	None	Node(5)->left = nullptr	No change
12	Build right subtree of 5	[5..4]	None	Node(5)->right = nullptr	No change
13	Build right subtree of 6	[6..6]	Node(7)	Node(6)->right = Node(7)	4 / \ 2 6 / \ / \ 1 3 5 7
14	Build left subtree of 7	[6..5]	None	Node(7)->left = nullptr	No change
15	Build right subtree of 7	[7..6]	None	Node(7)->right = nullptr	No change
16	Return root node	N/A	N/A	N/A	Balanced BST complete

💡 Recursion ends when left > right, no nodes created for empty subarrays.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	After Step 13	Final
left	0	0	0	0	0	4	6	N/A
right	6	6	2	0	2	6	6	N/A
mid	N/A	3	1	0	2	5	6	N/A
root	nullptr	Node(4)	Node(4)	Node(4)	Node(4)	Node(4)	Node(4)	Node(4)
current node	N/A	Node(4)	Node(2)	Node(1)	Node(3)	Node(6)	Node(7)	N/A

Key Moments - 3 Insights

Why do we pick the middle element as root?

Picking the middle element (see Step 1 in execution_table) ensures the tree is balanced because left and right subarrays have nearly equal sizes.

What happens when the subarray is empty?

When left > right (e.g., Step 4), recursion returns nullptr, meaning no node is created, stopping further branching.

How do left and right pointers get assigned?

After creating a node, recursive calls assign left and right children (see Steps 2, 6, 9, 13) by attaching returned nodes to pointers.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, 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 6 row in execution_table under 'Node Created' and 'Pointer Changes'

At which step does the recursion stop for the left subtree of Node(1)?

A Step 5

B Step 4

C Step 7

D Step 8

💡 Hint

Look for subarray range where left > right and no node created in execution_table

If the input array had 5 elements instead of 7, how would the root node change?

A Root would be the last element

B Root would be the first element

C Root would be the middle element of the 5 elements

D Root would be the average of all elements

💡 Hint

Recall the concept_flow and Step 1 where middle element is chosen as root

Concept Snapshot

Convert Sorted Array to Balanced BST:
- Pick middle element as root
- Recursively build left subtree from left subarray
- Recursively build right subtree from right subarray
- Base case: empty subarray returns nullptr
- Result is height-balanced BST

Full Transcript

This concept converts a sorted array into a balanced binary search tree by recursively selecting the middle element as the root node. The left half of the array forms the left subtree, and the right half forms the right subtree. The recursion stops when the subarray is empty. Each step creates nodes and attaches them as left or right children, ensuring the tree remains balanced. The execution table traces each recursive call, node creation, and pointer assignment, showing the tree's growth visually. Key moments clarify why the middle element is chosen, how recursion ends, and how pointers are assigned. The visual quiz tests understanding of node creation and recursion stopping points. The snapshot summarizes the process in simple 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 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