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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given a sorted array, a balanced binary search tree (BST) is created by picking the middle element as root, then recursively doing the same for left and right subarrays.
What is the inorder traversal output of the BST created from the array [1, 2, 3, 4, 5]?

DSA Rust

fn inorder_traversal(root: &Option<Box<TreeNode>>) -> Vec<i32> {
    match root {
        None => vec![],
        Some(node) => {
            let mut left = inorder_traversal(&node.left);
            left.push(node.val);
            left.extend(inorder_traversal(&node.right));
            left
        }
    }
}

// TreeNode struct
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

// Assume balanced BST is built correctly from [1,2,3,4,5]
// What does inorder_traversal(root) return?

A [1, 2, 3, 4, 5]

B [2, 1, 3, 4, 5]

C [5, 4, 3, 2, 1]

D [3, 2, 1, 4, 5]

💡 Hint

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

Inorder traversal visits left subtree, root, then right subtree. For a BST, this returns elements in ascending order. Since the tree is balanced but BST property holds, the output is the sorted array itself.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

If you build a balanced binary search tree (BST) from a sorted array of length n, what is the height of the resulting BST in terms of n?

A O(n log n)

B O(n)

C O(log n)

D O(1)

💡 Hint

Balanced BST splits array in half at each level.

Each level of the tree splits the array roughly in half, so the height grows logarithmically with the number of elements.

🔧 Debug

advanced

Identify the Bug in BST Construction Code

This Rust function is intended to build a balanced BST from a sorted array. What error will it cause when run?

DSA Rust

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

A No error, code runs correctly

B Compilation error due to missing semicolon

C Runtime panic due to index out of bounds

D Stack overflow due to infinite recursion

💡 Hint

Check the slice passed to the right subtree recursive call.

The right subtree call uses nums[mid..], which includes nums[mid] again, causing infinite recursion on the same slice.

📝 Syntax

advanced

Correct Rust Syntax for TreeNode Definition

Which option correctly defines a TreeNode struct in Rust for a binary tree node with integer value and optional left and right children?

A

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

B

struct TreeNode {
    val: i32,
    left: Box<Option<TreeNode>>,
    right: Box<Option<TreeNode>>,
}

C

struct TreeNode {
    val: i32,
    left: Option<TreeNode>,
    right: Option<TreeNode>,
}

D

struct TreeNode {
    val: i32,
    left: Box<TreeNode>,
    right: Box<TreeNode>,
}

💡 Hint

Children must be optional and boxed to allow recursive types.

Option A correctly uses Option> to allow nullable children and boxing for recursive type size.

🚀 Application

expert

Number of Nodes at Each Level in Balanced BST

You build a balanced BST from a sorted array of length 15. How many nodes are there at level 3 (root is level 1)?

A 8

B 4

C 2

D 1

💡 Hint

Each level doubles the number of nodes from the previous level in a full binary tree.

Level 1 has 1 node, level 2 has 2 nodes, level 3 has 4 nodes in a balanced binary tree.

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