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

Convert Sorted Array to Balanced BST

📖 Scenario: You are building a search feature for a phone book app. To make searching fast, you want to organize the contacts in a balanced tree structure.You have a sorted list of contact IDs, and you want to convert it into a balanced Binary Search Tree (BST) so that searching for any contact ID is quick.

🎯 Goal: Create a balanced BST from a sorted array of integers representing contact IDs.This will help the app find contacts quickly by minimizing the search steps.

📋 What You'll Learn

Create a sorted integer array called sortedContacts with the exact values: 1, 3, 5, 7, 9, 11, 13.

Create a class TreeNode with public integer val, and public TreeNode references left and right.

Create a method BuildBalancedBST that takes the array, start index, and end index, and returns the root TreeNode of the balanced BST.

Use recursion in BuildBalancedBST to pick the middle element as root and build left and right subtrees.

Print the BST nodes in in-order traversal to verify the tree structure.

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and search engines to quickly find data without scanning everything.

💼 Career

Understanding how to build balanced trees helps in roles like software development, data engineering, and system design where efficient data access is critical.

1

Create the sorted array of contact IDs

Create a sorted integer array called sortedContacts with these exact values: 1, 3, 5, 7, 9, 11, 13.

DSA C#

# Create the sortedContacts array with the exact values
# Your code here

Hint

Use int[] sortedContacts = new int[] {1, 3, 5, 7, 9, 11, 13}; to create the array.

2

Define the TreeNode class

Create a public class called TreeNode with a public integer field val, and public TreeNode fields left and right. Add a constructor that sets val.

DSA C#

int[] sortedContacts = new int[] {1, 3, 5, 7, 9, 11, 13};

// Define the TreeNode class below
# Your code here

Hint

Define a class with public fields and a constructor that sets the value.

3

Implement the BuildBalancedBST method

Create a public static method called BuildBalancedBST that takes int[] arr, int start, and int end as parameters and returns a TreeNode. Use recursion to build a balanced BST by choosing the middle element as root, then recursively build left and right subtrees.

DSA C#

int[] sortedContacts = new int[] {1, 3, 5, 7, 9, 11, 13};

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

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

// Implement BuildBalancedBST method below
# Your code here

Hint

Use recursion with base case start > end. Pick middle element as root and build left and right subtrees recursively.

4

Print the BST in in-order traversal

Create a public static method called InOrderTraversal that takes a TreeNode root and prints the node values in in-order (left, root, right). Then call InOrderTraversal with the root returned by BuildBalancedBST(sortedContacts, 0, sortedContacts.Length - 1).

DSA C#

int[] sortedContacts = new int[] {1, 3, 5, 7, 9, 11, 13};

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

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

public static TreeNode BuildBalancedBST(int[] arr, int start, int end)
{
    if (start > end)
    {
        return null;
    }

    int mid = (start + end) / 2;
    TreeNode node = new TreeNode(arr[mid]);

    node.left = BuildBalancedBST(arr, start, mid - 1);
    node.right = BuildBalancedBST(arr, mid + 1, end);

    return node;
}

// Implement InOrderTraversal method and print the BST below
# Your code here

Hint

Use recursion to print left subtree, then root value, then right subtree. Call InOrderTraversal with the root node.

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