Convert Sorted Array to Balanced BST in DSA Rust - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing data that needs to be organized for fast searching. To do this, you will convert this sorted list into a balanced Binary Search Tree (BST). A balanced BST keeps the tree height small, making searches quick.

🎯 Goal: Build a balanced Binary Search Tree from a sorted array of integers. You will create the data structure, set up helper variables, write the logic to build the tree, and finally print the tree in order.

📋 What You'll Learn

Create a sorted array called nums with the exact values [1, 2, 3, 4, 5, 6, 7].

Create a struct called TreeNode with fields val: i32, left: Option>, and right: Option>.

Write a function called sorted_array_to_bst that takes a slice of i32 and returns an Option> representing the root of the balanced BST.

Print the values of the BST in-order using a function called inorder_traversal.

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and file systems to keep data organized for fast searching and insertion.

💼 Career

Understanding how to convert sorted data into balanced trees is important for software engineers working with search algorithms and data indexing.

1

Create the sorted array nums

Create a variable called nums and set it to the sorted array [1, 2, 3, 4, 5, 6, 7].

DSA Rust

# Create the sorted array nums
# Your code here

Hint

Use let nums = [1, 2, 3, 4, 5, 6, 7]; to create the array.

2

Define the TreeNode struct

Define a struct called TreeNode with three fields: val: i32, left: Option>, and right: Option>.

DSA Rust

let nums = [1, 2, 3, 4, 5, 6, 7];

// Define the TreeNode struct
# Your code here

Hint

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

3

Write the sorted_array_to_bst function

Write a function called sorted_array_to_bst that takes a slice nums: &[i32] and returns Option>. Use the middle element as root, recursively build left and right subtrees from the left and right halves of the slice.

DSA Rust

let nums = [1, 2, 3, 4, 5, 6, 7];

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

// Write sorted_array_to_bst function
# Your code here

Hint

Use recursion and find the middle index with nums.len() / 2.

4

Print the BST values in-order

Write a function called inorder_traversal that takes root: &Option> and prints the values in ascending order separated by spaces. Then call inorder_traversal on the BST created from nums.

DSA Rust

let nums = [1, 2, 3, 4, 5, 6, 7];

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

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..]),
    }))
}

// Write inorder_traversal function and call it
# Your code here

Hint

Traverse left subtree, print root value, then traverse right subtree recursively.

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