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

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

Execution Sample

DSA C#

public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
        left = right = null;
    }
}

public Node SortedArrayToBST(int[] arr, int start, int end) {
    if (start > end) return null;
    int mid = start + (end - start) / 2;
    Node node = new Node(arr[mid]);
    node.left = SortedArrayToBST(arr, start, mid - 1);
    node.right = SortedArrayToBST(arr, mid + 1, end);
    return node;
}

// Example usage:
int[] arr = {1, 2, 3, 4, 5, 6, 7};
Node root = SortedArrayToBST(arr, 0, arr.Length - 1);

Builds a balanced BST by choosing 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 [0..6]	[1,2,3,4,5,6,7]	Node(4)	root = Node(4)	4
2	Build left subtree [0..2]	[1,2,3]	Node(2)	root.left = Node(2)	4 / 2
3	Build left subtree of Node(2) [0..0]	[1]	Node(1)	Node(2).left = Node(1)	4 / 2 / 1
4	Build left subtree of Node(1) [0..-1]	[]	null	Node(1).left = null	No change
5	Build right subtree of Node(1) [1..0]	[]	null	Node(1).right = null	No change
6	Build right subtree of Node(2) [2..2]	[3]	Node(3)	Node(2).right = Node(3)	4 / 2 / \ 1 3
7	Build left subtree of Node(3) [2..1]	[]	null	Node(3).left = null	No change
8	Build right subtree of Node(3) [3..2]	[]	null	Node(3).right = null	No change
9	Build right subtree [4..6]	[5,6,7]	Node(6)	root.right = Node(6)	4 / \ 2 6 / \
10	Build left subtree of Node(6) [4..4]	[5]	Node(5)	Node(6).left = Node(5)	4 / \ 2 6 / \ / 1 3 5
11	Build left subtree of Node(5) [4..3]	[]	null	Node(5).left = null	No change
12	Build right subtree of Node(5) [5..4]	[]	null	Node(5).right = null	No change
13	Build right subtree of Node(6) [6..6]	[7]	Node(7)	Node(6).right = Node(7)	4 / \ 2 6 / \ / \ 1 3 5 7
14	Build left subtree of Node(7) [6..5]	[]	null	Node(7).left = null	No change
15	Build right subtree of Node(7) [7..6]	[]	null	Node(7).right = null	No change
16	Return root	Full tree built	N/A	N/A	Balanced BST with root 4

💡 All subarrays processed; recursion ends when start > end.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 9	Final
start	0	0	0	4	N/A
end	6	6	2	6	N/A
mid	N/A	3	1	5	N/A
root	null	Node(4)	Node(4)	Node(4)	Node(4)
current node	null	Node(4)	Node(2)	Node(6)	N/A

Key Moments - 3 Insights

Why do we pick the middle element as root instead of the first or last?

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 for left and right subtrees.

What happens when the subarray is empty (start > end)?

When start > end (e.g., Step 4), the function returns null, meaning no node is created, which stops recursion and sets leaf children to null.

How do left and right pointers get assigned correctly?

After creating a node, recursive calls build left and right subtrees from subarrays (Steps 2 and 9), and their returned nodes are assigned to node.left and node.right respectively.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, which node is assigned as the right child of Node(2)?

A Node(1)

B Node(3)

C Node(4)

D Node(5)

💡 Hint

Check the 'Pointer Changes' and 'Node Created' columns at Step 6.

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

A Step 4

B Step 5

C Step 7

D Step 3

💡 Hint

Look for when the subarray range is empty and null is returned for Node(1).left.

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

A Root would be the 5th element

B Root would be the 3rd element

C Root would be the 4th element

D Root would be the 6th element

💡 Hint

Recall that mid is calculated as start + (end - start) / 2. For indices 0 to 7: 0 + (7 - 0) / 2 = 3 (0-based), the 4th element (1-based).

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: start > end returns null
- Result is height-balanced BST

Full Transcript

This concept converts a sorted array into a balanced binary search tree by recursively choosing 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. This approach ensures the tree is balanced, with roughly equal nodes on each side. The execution table traces each recursive call, node creation, and pointer assignment, showing the tree growing step-by-step.

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 linked list from the array

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.

2. Step 2: Reason about balanced BST

   A balanced BST has roughly equal nodes on left and right subtrees, minimizing height and improving search efficiency.

3. Final Answer:

   To create a BST with minimum height -> Option A

4. Quick Check:

   Balanced BST = minimum height [OK]

Hint: Pick option about minimum height balanced BST [OK]

Common Mistakes:

• Confusing balanced BST with sorted linked list
• Thinking the array needs to be reversed
• Assuming sorting again is required

2. Which C# syntax correctly defines the base case for recursion when converting a sorted array to a balanced BST?

easy

A. if (start < end) return null;

B. if (start == end) return new TreeNode();

C. if (start > end) return null;

D. if (start != end) return new TreeNode();

Solution

1. Step 1: Identify base case condition

   When start index is greater than end index, it means no elements remain to form a node, so return null.

2. Step 2: Match correct syntax

   The correct syntax is "if (start > end) return null;" which stops recursion properly.

3. Final Answer:

   if (start > end) return null; -> Option C

4. Quick Check:

   Base case = start > end returns null [OK]

Hint: Base case stops when start index passes end index [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning new node instead of null in base case
• Using wrong comparison operators

3. What is the output tree structure (inorder traversal) after running this code snippet on array [1, 2, 3, 4, 5]?

TreeNode SortedArrayToBST(int[] nums, int start, int end) {
  if (start > end) return null;
  int mid = (start + end) / 2;
  TreeNode node = new TreeNode(nums[mid]);
  node.left = SortedArrayToBST(nums, start, mid - 1);
  node.right = SortedArrayToBST(nums, mid + 1, end);
  return node;
}

var root = SortedArrayToBST(new int[] {1, 2, 3, 4, 5}, 0, 4);
PrintInorder(root);

medium

A. 2 -> 1 -> 3 -> 4 -> 5 -> null

B. 3 -> 2 -> 1 -> 4 -> 5 -> null

C. 5 -> 4 -> 3 -> 2 -> 1 -> null

D. 1 -> 2 -> 3 -> 4 -> 5 -> null

Solution

1. Step 1: Understand inorder traversal

   Inorder traversal of BST visits left subtree, root, then right subtree, producing sorted order.

2. Step 2: Trace the code output

   The code builds a balanced BST from sorted array, so inorder traversal outputs original sorted array: 1, 2, 3, 4, 5.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> null -> Option D

4. Quick Check:

   Inorder traversal = sorted array [OK]

Hint: Inorder traversal of BST equals sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming output is reversed
• Misunderstanding recursion mid calculation

4. Identify the bug in this C# method converting a sorted array to a balanced BST:

TreeNode SortedArrayToBST(int[] nums, int start, int end) {
  if (start >= end) return null;
  int mid = (start + end) / 2;
  TreeNode node = new TreeNode(nums[mid]);
  node.left = SortedArrayToBST(nums, start, mid - 1);
  node.right = SortedArrayToBST(nums, mid + 1, end);
  return node;
}

medium

A. Base case condition should be start > end, not start >= end

B. Mid calculation should use (start + end + 1) / 2

C. Left subtree call should be from start to mid

D. Right subtree call should be from mid to end

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly returns null when start == end, skipping valid single element nodes.

2. Step 2: Correct base case condition

   It should return null only when start > end, allowing nodes when start == end.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option A

4. Quick Check:

   Base case = start > end returns null [OK]

Hint: Base case must allow single element nodes (start == end) [OK]

Common Mistakes:

• Using >= instead of > in base case
• Changing mid calculation unnecessarily
• Incorrect subtree index ranges

5. Given a sorted array with duplicate values [1, 2, 2, 3, 4], how should the balanced BST construction handle duplicates to maintain BST properties?

hard

A. Place duplicates randomly in left or right subtree

B. Place duplicates consistently in the right subtree

C. Ignore duplicates during BST construction

D. Place duplicates consistently in the left subtree

Solution

1. Step 1: Understand BST property with duplicates

   BST requires left subtree values less than root, right subtree values greater or equal to root for duplicates.

2. Step 2: Decide duplicate placement

   Placing duplicates consistently in the right subtree maintains BST property and balanced structure.

3. Final Answer:

   Place duplicates consistently in the right subtree -> Option B

4. Quick Check:

   Duplicates go right subtree to keep BST valid [OK]

Hint: Put duplicates in right subtree to keep BST valid [OK]

Common Mistakes:

• Placing duplicates randomly breaking BST rules
• Ignoring duplicates causing data loss
• Placing duplicates in left subtree breaking order