Convert Sorted Array to Balanced BST in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index of the array.

DSA Go

mid := (start + [1]) / 2

Drag options to blanks, or click blank then click option'

Aend

Blen(arr)

C0

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(arr) instead of end index.

Using start twice instead of end.

The middle index is calculated by averaging the start and end indices.

2fill in blank

medium

Complete the code to create a new tree node with the middle element.

DSA Go

node := &TreeNode{Val: [1]

Drag options to blanks, or click blank then click option'

Aarr[mid]

Barr[end]

Carr[start]

Darr[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr[start] or arr[end] instead of arr[mid].

Using arr[0] which is always the first element.

The root node value is the middle element of the current array segment.

3fill in blank

hard

Fix the error in the recursive call to build the left subtree.

DSA Go

node.Left = sortedArrayToBST(arr, start, [1])

Drag options to blanks, or click blank then click option'

Astart + 1

Bmid

Cmid - 1

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid as end index includes the middle element again.

Using end includes elements after mid.

The left subtree uses the array segment before the middle element, so end index is mid - 1.

4fill in blank

hard

Fill both blanks to build the right subtree correctly.

DSA Go

node.Right = sortedArrayToBST(arr, [1], [2])

Drag options to blanks, or click blank then click option'

Amid + 1

Bstart

Cend

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid as start includes middle element again.

Using start or mid incorrectly as end index.

The right subtree uses the array segment after the middle element, from mid + 1 to end.

5fill in blank

hard

Fill all three blanks to complete the base case and recursive call.

DSA Go

if [1] > [2] {
    return nil
}

mid := (start + end) / 2
node := &TreeNode{Val: arr[mid]}
node.Left = sortedArrayToBST(arr, start, [3])
return node

Drag options to blanks, or click blank then click option'

Astart

Bend

Cmid - 1

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start >= end in base case instead of >.

Using mid or mid + 1 for left subtree end index.

The base case checks if start > end to stop recursion. The left subtree uses end index mid - 1.

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 minimal height for efficient search

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 build a BST that is balanced, meaning the tree height is minimized to allow fast searching.

2. Step 2: Why minimal height matters

   A balanced BST ensures operations like search, insert, and delete run in O(log n) time, which is efficient.

3. Final Answer:

   To create a BST with minimal height for efficient search -> Option A

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Pick option about minimal height for balanced BST [OK]

Common Mistakes:

• Confusing BST with linked list
• Thinking sorting again is needed
• Ignoring tree balance importance

2. Which Go function signature correctly represents the recursive function to convert a sorted array to a balanced BST?

easy

A. func sortedArrayToBST(nums []int) *TreeNode

B. func sortedArrayToBST(nums int) TreeNode

C. func sortedArrayToBST(nums []int) int

D. func sortedArrayToBST(nums []int) []int

Solution

1. Step 1: Identify input and output types

   The function takes a slice of integers (sorted array) and returns a pointer to the root TreeNode of the BST.

2. Step 2: Match correct Go syntax

   func sortedArrayToBST(nums []int) *TreeNode matches: input is []int, output is *TreeNode pointer, which is standard for tree nodes in Go.

3. Final Answer:

   func sortedArrayToBST(nums []int) *TreeNode -> Option A

4. Quick Check:

   Input []int, output *TreeNode pointer [OK]

Hint: Look for slice input and pointer to TreeNode output [OK]

Common Mistakes:

• Using int instead of slice for input
• Returning int or slice instead of TreeNode pointer
• Missing pointer in return type

3. Given the sorted array [1, 2, 3, 4, 5], what is the root value of the balanced BST created by the standard algorithm?

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Find middle element of array

   The middle index of [1, 2, 3, 4, 5] is 2 (0-based), so middle element is 3.

2. Step 2: Root is middle element

   The root of the balanced BST is the middle element to balance left and right subtrees.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Middle element = root = 3 [OK]

Hint: Root is middle element of sorted array [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one error in middle index
• Confusing index with value

4. Consider this Go code snippet to convert a sorted array to a balanced BST:

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid:])
    return root
}

What is the bug in this code?

medium

A. The function should return an int, not *TreeNode

B. The base case should check for len(nums) < 0

C. The root node is created with wrong value

D. The right subtree slice should start from mid+1, not mid

Solution

1. Step 1: Analyze slicing for right subtree

   The right subtree slice uses nums[mid:], which includes the middle element again, causing duplicate nodes.

2. Step 2: Correct slice to exclude middle element

   Right subtree should start from mid+1 to avoid including root again.

3. Final Answer:

   The right subtree slice should start from mid+1, not mid -> Option D

4. Quick Check:

   Right slice = nums[mid+1:] to avoid duplicates [OK]

Hint: Right slice must exclude middle element by starting at mid+1 [OK]

Common Mistakes:

• Using mid instead of mid+1 for right slice
• Wrong base case condition
• Returning wrong type

5. You have a sorted array [10, 20, 30, 40, 50, 60, 70]. After converting it to a balanced BST, what is the inorder traversal of the BST?

hard

A. [10, 30, 20, 50, 40, 70, 60]

B. [10, 20, 30, 40, 50, 60, 70]

C. [70, 60, 50, 40, 30, 20, 10]

D. [40, 20, 10, 30, 60, 50, 70]

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal visits nodes in ascending order for BST, so it returns the sorted array.

2. Step 2: Confirm traversal matches original array

   Since the BST is built from sorted array, inorder traversal outputs the same sorted sequence.

3. Final Answer:

   [10, 20, 30, 40, 50, 60, 70] -> Option B

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 traversal changes order
• Mixing up traversal outputs