Convert Sorted Array to Balanced BST in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given the following C# code that converts a sorted array to a balanced binary search tree (BST), what is the output of the inorder traversal of the BST?

DSA C#

using System;
using System.Collections.Generic;

class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; left = right = null; }
}

class Program {
    static TreeNode SortedArrayToBST(int[] nums) {
        return Helper(nums, 0, nums.Length - 1);
    }

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

    static void Inorder(TreeNode root, List<int> result) {
        if (root == null) return;
        Inorder(root.left, result);
        result.Add(root.val);
        Inorder(root.right, result);
    }

    static void Main() {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7};
        TreeNode bstRoot = SortedArrayToBST(sortedArray);
        List<int> inorderResult = new List<int>();
        Inorder(bstRoot, inorderResult);
        Console.WriteLine(string.Join(", ", inorderResult));
    }
}

A 1, 2, 3, 4, 5, 6, 7

B 4, 2, 1, 3, 6, 5, 7

C 7, 6, 5, 4, 3, 2, 1

D 1, 3, 2, 5, 4, 7, 6

💡 Hint

Inorder traversal of a BST always returns the elements in sorted order.

The code builds a balanced BST by choosing the middle element as root recursively. Inorder traversal visits nodes in ascending order, so the output matches the original sorted array.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

If you convert a sorted array of length 15 into a balanced binary search tree using the middle element as root recursively, what is the height of the resulting BST?

A 3

B 5

C 4

D 6

💡 Hint

Height of a balanced BST is approximately log2(n+1).

A balanced BST built from 15 nodes has height floor(log2(15)) + 1 = 4.

🔧 Debug

advanced

Identify the Bug in BST Construction

What error will occur if the base case in the helper function is changed from 'if (left > right) return null;' to 'if (left >= right) return null;' in the sorted array to BST conversion?

DSA C#

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

A The BST will be missing some nodes

B NullReferenceException when accessing node

C No error, code runs correctly

D StackOverflowException due to infinite recursion

💡 Hint

Check what happens when left == right in the base case.

Changing to 'left >= right' causes the function to skip creating nodes when left == right, missing leaf nodes and resulting in an incomplete BST.

❓ Predict Output

advanced

Output of Preorder Traversal of Balanced BST

What is the output of the preorder traversal of the balanced BST created from the sorted array [10, 20, 30, 40, 50] using the standard middle element method?

DSA C#

using System;
using System.Collections.Generic;

class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int x) { val = x; left = right = null; }
}

class Program {
    static TreeNode SortedArrayToBST(int[] nums) {
        return Helper(nums, 0, nums.Length - 1);
    }

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

    static void Preorder(TreeNode root, List<int> result) {
        if (root == null) return;
        result.Add(root.val);
        Preorder(root.left, result);
        Preorder(root.right, result);
    }

    static void Main() {
        int[] sortedArray = {10, 20, 30, 40, 50};
        TreeNode bstRoot = SortedArrayToBST(sortedArray);
        List<int> preorderResult = new List<int>();
        Preorder(bstRoot, preorderResult);
        Console.WriteLine(string.Join(", ", preorderResult));
    }
}

A 30, 10, 40, 20, 50

B 30, 10, 20, 40, 50

C 30, 20, 40, 10, 50

D 30, 20, 10, 40, 50

💡 Hint

Preorder traversal visits root, then left subtree, then right subtree.

The middle element 30 is root, left subtree is [10,20], right subtree is [40,50]. Preorder visits root 30, then left subtree preorder (10,20), then right subtree preorder (40,50).

🧠 Conceptual

expert

Minimum Number of Nodes in Balanced BST of Height 5

What is the minimum number of nodes in a balanced binary search tree of height 5?

A 32

B 15

C 31

D 16

💡 Hint

Use the formula for minimum nodes in AVL tree: N(h) = 1 + N(h-1) + N(h-2), with N(0)=1, N(1)=2.

The minimum nodes in balanced BST of height h follows Fibonacci-like sequence. For height 5, minimum nodes = 16.

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