Convert Sorted Array to Balanced BST in DSA Rust - Execution Trace

Concept Flow - Convert Sorted Array to Balanced BST

Start with sorted array

↓

Find middle element

→Create root node with middle

↓

Left subarray

→Recursively build left subtree

↓

Right subarray

→Recursively build right subtree

↓

Attach left and right subtrees to root

↓

Return balanced BST root

We pick the middle element as root to keep the tree balanced, then recursively do the same for left and right subarrays to build left and right subtrees.

Execution Sample

DSA Rust

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

This function converts a sorted array into a balanced binary search tree by recursively choosing the middle element as root.

Execution Table

Step	Operation	Subarray	Middle Index	Node Created	Left Subtree Call	Right Subtree Call	Visual State
1	Start	[1, 2, 3, 4, 5, 6, 7]	3	Node(4)	Call with [1,2,3]	Call with [5,6,7]	4
2	Left subtree root	[1, 2, 3]	1	Node(2)	Call with [1]	Call with [3]	2 <- 4
3	Left subtree left leaf	[1]	0	Node(1)	Call with []	Call with []	1 <- 2 <- 4
4	Left subtree right leaf	[3]	0	Node(3)	Call with []	Call with []	1,3 <- 2 <- 4
5	Right subtree root	[5, 6, 7]	1	Node(6)	Call with [5]	Call with [7]	2,6 <- 4
6	Right subtree left leaf	[5]	0	Node(5)	Call with []	Call with []	5 <- 6 <- 4
7	Right subtree right leaf	[7]	0	Node(7)	Call with []	Call with []	5,7 <- 6 <- 4
8	Attach subtrees	N/A	N/A	Root(4)	Left subtree root(2)	Right subtree root(6)	Balanced BST: 4 / \ 2 6 / \ / \ 1 3 5 7
9	Return	N/A	N/A	Balanced BST root	N/A	N/A	Final balanced BST returned
10	Exit	N/A	N/A	N/A	N/A	N/A	All recursive calls completed

💡 All subarrays processed, BST fully built and returned

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	Final
arr	[1,2,3,4,5,6,7]	[1,2,3,4,5,6,7]	[1,2,3]	[5,6,7]	N/A
mid	N/A	3	1	1	N/A
root.val	N/A	4	2	6	4
left subtree	N/A	Call with [1,2,3]	Call with [1]	Call with [5]	Nodes 1,2,3 attached
right subtree	N/A	Call with [5,6,7]	Call with [3]	Call with [7]	Nodes 5,6,7 attached

Key Moments - 3 Insights

Why do we pick the middle element as the root?

Picking the middle element (see Step 1 and Step 2 in execution_table) ensures the left and right subtrees have roughly equal size, keeping the tree balanced.

What happens when the subarray is empty?

When the subarray is empty (like in Step 3 and Step 4 calls), the function returns None, meaning no node is created, which stops recursion on that branch.

How do left and right recursive calls build the tree?

Each recursive call (see Left subtree Call and Right subtree Call columns) builds subtrees from left and right halves, which are then attached to the current node to form the BST.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the middle index chosen for the left subtree?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Middle Index' column at Step 2 in the execution_table.

At which step does the function create the root node of the right subtree?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Node Created' and 'Operation' columns in execution_table for the right subtree root.

If the input array was empty, what would the function return?

A A leaf node

B A node with value 0

C None (no node)

D An error

💡 Hint

Refer to the key_moments explanation about empty subarrays and recursion stopping.

Concept Snapshot

Convert Sorted Array to Balanced BST:
- Pick middle element as root
- Recursively build left subtree from left half
- Recursively build right subtree from right half
- Base case: empty array returns None
- Result is a balanced BST with minimal height

Full Transcript

This concept converts a sorted array into a balanced binary search tree by choosing the middle element as the root node. The function recursively applies the same logic to the left and right halves of the array to build left and right subtrees. When the subarray is empty, recursion stops by returning None. This approach ensures the tree is balanced, with roughly equal nodes on each side. The execution table shows each step creating nodes and recursive calls, building the tree from bottom up. Key moments clarify why the middle element is chosen and how recursion stops. The visual quiz tests understanding of middle index selection, subtree roots, and base cases.

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