Convert Sorted Array to Balanced BST in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Balanced Binary Search Tree (BST)?

A Balanced BST is a tree where the left and right subtrees of every node differ in height by at most one. This keeps the tree height minimal, ensuring efficient search, insert, and delete operations.

beginner

Why use the middle element of a sorted array to create a Balanced BST?

Choosing the middle element as the root splits the array into two equal halves. This ensures the left and right subtrees have roughly the same number of nodes, keeping the tree balanced.

beginner

What is the base case when recursively converting a sorted array to a Balanced BST?

The base case occurs when the start index is greater than the end index, meaning there are no elements left to process. At this point, return None (no node).

intermediate

In Rust, what data structure is commonly used to represent a BST node?

A BST node is often represented using a struct with fields for the value and optional boxed pointers to left and right child nodes, like Option.

intermediate

What is the time complexity of converting a sorted array to a Balanced BST?

The time complexity is O(n), where n is the number of elements in the array, because each element is visited once to create nodes.

What element should be chosen as the root when converting a sorted array to a Balanced BST?

A Any random element

B The first element

C The last element

D The middle element

Choosing the middle element ensures the tree remains balanced by splitting the array into two equal halves.

What does the base case in the recursive function for building a Balanced BST from a sorted array check?

A If the array is empty

B If start index equals end index

C If start index is greater than end index

D If the middle element is zero

The recursion stops when the start index is greater than the end index, meaning no elements remain to process.

What Rust type is used to represent a node that may or may not exist in a BST?

A Box<TreeNode>

B Option<Box<TreeNode>>

C Vec<TreeNode>

D TreeNode

Option> allows representing either a node (Some) or no node (None), which is essential for tree structures.

What is the time complexity of building a Balanced BST from a sorted array of size n?

A O(n)

B O(log n)

C O(n log n)

D O(n^2)

Each element is processed once to create a node, so the time complexity is linear, O(n).

Which traversal method would print the elements of the Balanced BST in sorted order?

A In-order traversal

B Pre-order traversal

C Post-order traversal

D Level-order traversal

In-order traversal visits nodes in ascending order for a BST.

Explain step-by-step how to convert a sorted array into a Balanced BST using recursion.

Think about dividing the array and building subtrees.

Describe how a Balanced BST node is represented in Rust and why Option> is used.

Consider Rust's ownership and recursive data types.

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