Convert Sorted Array to Balanced BST in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal when converting a sorted array to a balanced BST?

To create a binary search tree where the height difference between left and right subtrees is minimized, ensuring efficient search operations.

beginner

Why do we choose the middle element of the sorted array as the root in this conversion?

Choosing the middle element splits the array into two halves of roughly equal size, helping to keep the tree balanced.

intermediate

What is the time complexity of converting a sorted array to a balanced BST?

O(n), where n is the number of elements in the array, because each element is visited once to create nodes.

beginner

In the recursive approach, what are the base cases when building the BST?

When the start index is greater than the end index, it means no elements are left to process, so return null.

intermediate

How does the recursive function ensure the left and right subtrees are balanced?

By recursively choosing the middle element of the left half for the left subtree and the middle element of the right half for the right subtree.

What element is chosen as the root when converting a sorted array to a balanced BST?

A The first element

B The middle element

C The last element

D A random element

The middle element splits the array into two halves, helping to keep the BST balanced.

What is the time complexity of building a balanced BST from a sorted array?

A O(n)

B O(n log n)

C O(log n)

D O(n^2)

Each element is processed once, so the time complexity is O(n).

What does the base case in the recursive function check for?

A If the middle element is null

B If the array is empty

C If start index is greater than end index

D If the tree is balanced

When start index > end index, there are no elements left to process, so recursion stops.

Which traversal order is naturally followed when building the BST recursively from the sorted array?

A Postorder (left, right, root)

B Inorder (left, root, right)

C Level order

D Preorder (root, left, right)

The root is created first (middle element), then left and right subtrees are built recursively.

What property does the resulting BST have after conversion from a sorted array?

A It is balanced and maintains BST order

B It is a max heap

C It is a linked list

D It is unbalanced

The tree is balanced and maintains the binary search tree property.

Explain step-by-step how to convert a sorted array into a balanced binary search tree.

Think about dividing the array and building subtrees recursively.

Describe why the balanced BST created from a sorted array is efficient for search operations.

Consider how tree height relates to search speed.

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