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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Rust

let mid = (start + [1]) / 2;

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

Alen

Bstart

C0

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using start twice instead of end

Using length 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 TreeNode with the middle element as value.

DSA Rust

let node = TreeNode::new([1][mid]);

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

Anums

Barr

Cvec

Dlist

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable name like vec or arr

Using list which is not defined

The input array is named nums, so we access nums[mid] to get the middle element.

3fill in blank

hard

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

DSA Rust

node.left = build_bst(nums, start, [1] - 1);

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

Amid

Bend

Cstart

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start or end incorrectly

Using mid + 1 which is for right subtree

The left subtree uses the range from start to mid - 1.

4fill in blank

hard

Fill both blanks to build the right subtree correctly.

DSA Rust

node.right = build_bst(nums, [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 or start incorrectly

Swapping start and end

The right subtree covers the range from mid + 1 to end.

5fill in blank

hard

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

DSA Rust

if [1] > [2] {
    return None;
}

let mid = (start + end) / 2;
let mut node = TreeNode::new(nums[mid]);
node.left = build_bst(nums, start, mid - 1);
node.right = build_bst(nums, mid + 1, [3]);
Some(Box::new(node))

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

Astart

Bend

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping start and end in base case

Using start instead of end for right subtree end

The base case checks if start is greater than end. The right subtree ends at end.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To sort the array again inside the BST

B. To reverse the array elements in the BST

C. To create a linked list from the array

D. To create a BST with minimal height for efficient search

Solution

1. Step 1: Understand the problem goal

   The goal is to build a BST that is balanced, meaning the tree height is minimized for fast search operations.

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 D

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Pick option about minimal height and efficiency [OK]

Common Mistakes:

• Thinking BST should reverse array order
• Confusing BST with linked list
• Ignoring balance and height importance

2. Which Rust function signature correctly represents a function that converts a sorted slice of integers into a balanced BST node?

easy

A. fn sorted_array_to_bst(nums: &[i32]) -> Option

B. fn sorted_array_to_bst(nums: Vec<i32>) -> TreeNode

C. fn sorted_array_to_bst(nums: &mut [i32]) -> TreeNode

D. fn sorted_array_to_bst(nums: &[i32]) -> TreeNode

Solution

1. Step 1: Analyze input parameter type

   The function should accept a slice reference &[i32] to avoid ownership issues and allow read-only access.

2. Step 2: Analyze return type

   Since the BST node can be empty, returning Option is correct to represent possible None or Some node.

3. Final Answer:

   fn sorted_array_to_bst(nums: &[i32]) -> Option -> Option A

4. Quick Check:

   Slice input + Option boxed node = correct signature [OK]

Hint: Look for slice input and Option return [OK]

Common Mistakes:

• Using Vec instead of slice for input
• Returning TreeNode directly without Option
• Using mutable slice when not needed

3. Given the Rust code below, what is the root node value of the balanced BST created from the sorted array?

fn sorted_array_to_bst(nums: &[i32]) -> Option {
    if nums.is_empty() { return None; }
    let mid = nums.len() / 2;
    Some(Box::new(TreeNode {
        val: nums[mid],
        left: sorted_array_to_bst(&nums[..mid]),
        right: sorted_array_to_bst(&nums[mid+1..]),
    }))
}

let nums = [1, 2, 3, 4, 5];
let root = sorted_array_to_bst(&nums);

medium

A. 5

B. 2

C. 3

D. 4

Solution

1. Step 1: Calculate middle index

   Array length is 5, mid = 5 / 2 = 2 (integer division).

2. Step 2: Identify root value

   Root node value is nums[2] = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Middle element = root = 3 [OK]

Hint: Middle index = length/2; root = nums[mid] [OK]

Common Mistakes:

• Using mid = (len-1)/2 causing off-by-one
• Choosing first or last element as root
• Confusing left and right subtree indices

4. Identify the bug in this Rust function that attempts to convert a sorted array to a balanced BST:

fn sorted_array_to_bst(nums: &[i32]) -> Option {
    if nums.len() == 0 {
        return None;
    }
    let mid = nums.len() / 2;
    Some(Box::new(TreeNode {
        val: nums[mid],
        left: sorted_array_to_bst(&nums[mid..]),
        right: sorted_array_to_bst(&nums[mid+1..]),
    }))
}

medium

A. Left subtree uses nums[mid..] instead of nums[..mid]

B. Right subtree uses nums[mid+1..] which is correct

C. Base case should check for nums.is_empty()

D. Mid index calculation is incorrect

Solution

1. Step 1: Check left subtree slice

   Left subtree should use nums[..mid] to exclude mid element, but code uses nums[mid..], including mid again.

2. Step 2: Consequence of bug

   This causes infinite recursion or duplicate nodes because mid element repeats in left subtree.

3. Final Answer:

   Left subtree uses nums[mid..] instead of nums[..mid] -> Option A

4. Quick Check:

   Left slice must exclude mid [OK]

Hint: Left slice excludes mid: use nums[..mid] [OK]

Common Mistakes:

• Including mid element in left subtree slice
• Ignoring base case condition
• Miscomputing mid index

5. You want to convert a sorted array with duplicate values into a balanced BST. Which approach correctly handles duplicates to maintain BST properties?

hard

A. Skip duplicates when building the BST

B. Place duplicates consistently in the right subtree during recursion

C. Place duplicates randomly in left or right subtree

D. Place duplicates in the left subtree only

Solution

1. Step 1: Understand BST property with duplicates

   BST requires left subtree values < node value, right subtree values >= node value to handle duplicates consistently.

2. Step 2: Consistent placement of duplicates

   Placing duplicates always in the right subtree maintains order and balance without ambiguity.

3. Final Answer:

   Place duplicates consistently in the right subtree during recursion -> Option B

4. Quick Check:

   Duplicates in right subtree = BST property maintained [OK]

Hint: Always put duplicates in right subtree for BST [OK]

Common Mistakes:

• Skipping duplicates losing data
• Random placement breaking BST rules
• Putting duplicates only in left subtree