Convert Sorted Array to Balanced BST in DSA C#

Mental Model

We build a tree by picking the middle element as root to keep it balanced. Then we do the same for left and right parts.

Analogy: Imagine dividing a sorted list of books evenly to put on two shelves so both shelves hold about the same number of books.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Create a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

4
Array split: left=[1,2,3], right=[5,6,7]

Why: Middle element keeps tree balanced by dividing array evenly

Step 2: Build left subtree from [1,2,3], pick middle 2 as left child

    4
   / 
  2
Array split: left=[1], right=[3]

Why: Recursively pick middle to keep left subtree balanced

Step 3: Build left child of 2 from [1], pick 1

    4
   / 
  2
 / 
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3

    4
   / 
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5,6,7], pick middle 6 as right child of 4

    4
   / \
  2   6
 / \

Why: Middle element divides right half evenly

Step 6: Build left child of 6 from [5], pick 5

    4
   / \
  2   6
 / \ /
1  3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7

    4
   / \
  2   6
 / \ / \
1  3 5  7

Why: Single element becomes leaf node

Result:

Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Annotated Code

DSA C#

using System;

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

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return BuildBST(nums, 0, nums.Length - 1);
    }

    private TreeNode BuildBST(int[] nums, int left, int right) {
        if (left > right) return null; // base case: no elements

        int mid = left + (right - left) / 2; // find middle index
        TreeNode root = new TreeNode(nums[mid]); // middle element as root

        root.left = BuildBST(nums, left, mid - 1); // build left subtree
        root.right = BuildBST(nums, mid + 1, right); // build right subtree

        return root; // return root of this subtree
    }

    public void PrintInOrder(TreeNode root) {
        if (root == null) return;
        PrintInOrder(root.left);
        Console.Write(root.val + " ");
        PrintInOrder(root.right);
    }

    public static void Main() {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        Solution sol = new Solution();
        TreeNode root = sol.SortedArrayToBST(nums);
        sol.PrintInOrder(root);
        Console.WriteLine();
    }
}

if (left > right) return null; // base case: no elements

stop recursion when no elements left to process

int mid = left + (right - left) / 2; // find middle index

choose middle element to keep tree balanced

TreeNode root = new TreeNode(nums[mid]); // middle element as root

create node with middle element

root.left = BuildBST(nums, left, mid - 1); // build left subtree

recursively build left subtree from left half

root.right = BuildBST(nums, mid + 1, right); // build right subtree

recursively build right subtree from right half

return root; // return root of this subtree

return constructed subtree root

Output

1 2 3 4 5 6 7 

Complexity Analysis

Time: O(n) because each element is visited once to create a node

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Naive approach inserting nodes one by one into BST can be O(n^2) if unbalanced; this method guarantees balanced tree in O(n)

Edge Cases

empty array

returns null tree (no nodes)

DSA C#

if (left > right) return null; // base case: no elements

array with one element

creates single node tree

DSA C#

int mid = left + (right - left) / 2; // find middle index

array with two elements

root is first middle, one child on left or right

DSA C#

root.left = BuildBST(nums, left, mid - 1); // build left subtree

When to Use This Pattern

When you see a sorted array and need a balanced search tree, use the middle element as root and build subtrees recursively to keep balance.

Common Mistakes

Mistake: Picking first or last element as root instead of middle causes unbalanced tree
Fix: Always pick middle element to keep tree balanced

Mistake: Not handling base case when left > right leads to infinite recursion
Fix: Add base case to return null when no elements remain

Summary

Converts a sorted array into a balanced binary search tree by recursively choosing middle elements as roots.

Use when you want a balanced BST from sorted data for efficient search.

The key is picking the middle element each time to keep the tree balanced.

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