Convert Sorted Array to Balanced BST in DSA Rust

Mental Model

We build a tree by picking the middle element as root, then recursively do the same for left and right parts to keep it balanced.

Analogy: Imagine dividing a sorted list of books into two equal stacks by picking the middle book as the main one, then doing the same for each stack to keep shelves balanced.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Create a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

Tree: 4
Array split: left=[1,2,3], right=[5,6,7]

Why: Middle element keeps tree balanced by dividing array evenly

Step 2: Build left subtree from [1,2,3], pick middle 2 as left child

Tree:
    4
   /
  2
Array split left: [1], right: [3]

Why: Recursively pick middle to keep left subtree balanced

Step 3: Build left child of 2 from [1], which is 1

Tree:
    4
   /
  2
 /
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], which is 3

Tree:
    4
   /
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5,6,7], pick middle 6 as right child of 4

Tree:
    4
   / \
  2   6
 / \
1   3
Array split left: [5], right: [7]

Why: Recursively pick middle to keep right subtree balanced

Step 6: Build left child of 6 from [5], which is 5

Tree:
    4
   / \
  2   6
 / \  /
1   3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], which is 7

Tree:
    4
   / \
  2   6
 / \ / \
1  3 5  7

Why: Single element becomes leaf node

Result:

Balanced BST:
    4
   / \
  2   6
 / \ / \
1  3 5  7

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn sorted_array_to_bst(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
    if nums.is_empty() {
        return None;
    }
    let mid = nums.len() / 2; // find middle index
    let root = TreeNode::new(nums[mid]); // create root node
    root.borrow_mut().left = sorted_array_to_bst(&nums[..mid]); // build left subtree
    root.borrow_mut().right = sorted_array_to_bst(&nums[mid + 1..]); // build right subtree
    Some(root)
}

fn print_bst(root: &Option<Rc<RefCell<TreeNode>>>) {
    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, prefix: String, is_left: bool) {
        if let Some(n) = node {
            println!("{}{}{}", prefix, if is_left {"├── "} else {"└── "}, n.borrow().val);
            let new_prefix = prefix + if is_left {"│   "} else {"    "};
            helper(&n.borrow().left, new_prefix.clone(), true);
            helper(&n.borrow().right, new_prefix, false);
        }
    }
    helper(root, String::new(), false);
}

fn main() {
    let nums = [1, 2, 3, 4, 5, 6, 7];
    let bst_root = sorted_array_to_bst(&nums);
    print_bst(&bst_root);
}

let mid = nums.len() / 2; // find middle index

find middle element index to keep tree balanced

let root = TreeNode::new(nums[mid]); // create root node

create root node with middle element

root.borrow_mut().left = sorted_array_to_bst(&nums[..mid]); // build left subtree

recursively build left subtree from left half

root.borrow_mut().right = sorted_array_to_bst(&nums[mid + 1..]); // build right subtree

recursively build right subtree from right half

Output

└── 4

    ├── 2

    │   ├── 1

    │   └── 3

    └── 6

        ├── 5

        └── 7

Complexity Analysis

Time: O(n) because each element is visited once to create nodes

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Naive approach inserting elements one by one into BST can be O(n^2) if unbalanced; this method ensures balanced tree in O(n)

Edge Cases

empty array

returns None (empty tree)

DSA Rust

if nums.is_empty() { return None; }

single element array

creates a single node tree

DSA Rust

base case handled by recursion naturally

array with two elements

middle element chosen as root, one child on left or right

DSA Rust

mid calculation and recursive calls handle this

When to Use This Pattern

When you see a sorted array and need a balanced search tree, use the middle element as root and build subtrees recursively to keep balance.

Common Mistakes

Mistake: Choosing first or last element as root instead of middle
Fix: Always pick middle element index nums.len()/2 to keep tree balanced

Mistake: Not handling empty array base case causing infinite recursion
Fix: Add base case to return None when input slice is empty

Summary

Converts a sorted array into a balanced binary search tree by recursively choosing middle elements as roots.

Use when you want a balanced BST from sorted data for efficient search.

The key is picking the middle element each time to keep the tree balanced.

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