BST Insert Operation in DSA Rust - Build from Scratch

BST Insert Operation

📖 Scenario: You are building a simple phone book application that stores phone numbers in a Binary Search Tree (BST) for quick search and insertion.

🎯 Goal: Build a BST by inserting phone numbers one by one and then print the tree in an in-order traversal to see the sorted phone numbers.

📋 What You'll Learn

Create a BST node struct with value, left, and right fields

Create a root node variable called root initialized to None

Create a function called insert that inserts a value into the BST

Insert the given phone numbers into the BST using the insert function

Print the BST values in sorted order using in-order traversal

💡 Why This Matters

🌍 Real World

BSTs are used in phone books, contact lists, and databases to store and quickly retrieve sorted data.

💼 Career

Understanding BST insertions is fundamental for software engineers working with data structures, databases, and search algorithms.

1

Create the BST Node struct and root variable

Create a struct called Node with fields value: i32, left: Option, and right: Option. Then create a variable called root of type Option and set it to None.

DSA Rust

// Define the Node struct and create root variable
# Your code here

Hint

Use struct to define Node. Use Option<Box<Node>> for left and right to allow empty children.

2

Create the insert function for BST

Create a function called insert that takes root: &mut Option<Box<Node>> and value: i32. Insert the value into the BST by comparing with current node's value and inserting recursively into left or right subtree.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn insert(root: &mut Option>, value: i32) {
    // Your code here
}

fn main() {
    let mut root: Option> = None;
}

Hint

Use match on root. If None, create new node. If Some, compare values and recurse left or right.

3

Insert phone numbers into the BST

Use the insert function to insert these phone numbers into root: 5551234, 5555678, 5550000, 5559999, 5554321.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn insert(root: &mut Option>, value: i32) {
    match root {
        None => {
            *root = Some(Box::new(Node { value, left: None, right: None }));
        }
        Some(node) => {
            if value > = None;
    
    // Insert the phone numbers below
    // Your code here
}

Hint

Call insert(&mut root, value) for each phone number.

4

Print the BST values in sorted order

Create a function called in_order that takes root: &Option<Box<Node>> and prints the values in ascending order using in-order traversal. Then call in_order(&root) in main.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn insert(root: &mut Option>, value: i32) {
    match root {
        None => {
            *root = Some(Box::new(Node { value, left: None, right: None }));
        }
        Some(node) => {
            if value >) {
    // Your code here
}

fn main() {
    let mut root: Option> = None;
    insert(&mut root, 5551234);
    insert(&mut root, 5555678);
    insert(&mut root, 5550000);
    insert(&mut root, 5559999);
    insert(&mut root, 5554321);

    // Call in_order here
}

Hint

Use recursion to visit left child, print current node's value, then visit right child.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new value while keeping the BST property intact

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST property

   A BST keeps values in order: left child less, right child greater than parent.

2. Step 2: Purpose of insert

   Insert adds a new value so the tree remains ordered by BST rules.

3. Final Answer:

   To add a new value while keeping the BST property intact -> Option A

4. Quick Check:

   Insert = Add value maintaining order [OK]

Hint: Insert adds nodes keeping left < parent < right order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Believing insert finds max value

2. Which of the following Rust function signatures correctly represents a BST insert method that takes ownership of the tree node and returns the updated tree?

easy

A. fn insert(val: i32) -> Box<Node>

B. fn insert(&mut self, val: i32) -> &mut Node

C. fn insert(self: Box<Node>, val: i32) -> Box<Node>

D. fn insert(&self, val: i32) -> Box<Node>

Solution

1. Step 1: Understand ownership in Rust BST insert

   Insert usually takes ownership of the node (Box<Node>) and returns updated Box<Node>.

2. Step 2: Match signature to ownership pattern

   fn insert(self: Box<Node>, val: i32) -> Box<Node> matches: takes self as Box<Node>, returns Box<Node>. Others mismatch ownership or mutability.

3. Final Answer:

   fn insert(self: Box<Node>, val: i32) -> Box<Node> -> Option C

4. Quick Check:

   Ownership insert = self Box<Node> in, Box<Node> out [OK]

Hint: Insert owns node (Box), returns updated Box [OK]

Common Mistakes:

• Using &self instead of self for ownership
• Returning reference instead of Box<Node>
• Missing self parameter

3. Given the following Rust code snippet for inserting values into a BST, what will be the in-order traversal output after inserting 10, 5, 15, 7?

medium

A. [10, 5, 7, 15]

B. [5, 7, 10, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert values in BST order

   Insert 10 as root, 5 left of 10, 15 right of 10, 7 right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left, root, right: 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option B

4. Quick Check:

   In-order = sorted values [OK]

Hint: In-order traversal of BST = sorted inserted values [OK]

Common Mistakes:

• Confusing pre-order with in-order traversal
• Placing 7 as left child of 5 incorrectly
• Listing values in insertion order

4. Consider this Rust insert function snippet for a BST node:

fn insert(mut root: Option, val: i32) -> Option {
    if root.is_none() {
        return Some(Box::new(Node::new(val)));
    }
    if val < root.as_ref().unwrap().val {
        root.as_mut().unwrap().left = insert(root.as_mut().unwrap().left.take(), val);
    } else {
        root.as_mut().unwrap().right = insert(root.as_mut().unwrap().right.take(), val);
    }
    Some(root.unwrap())
}

What is the bug in this code?

medium

A. Calling unwrap() on root at the end consumes it, causing a move error

B. Not handling duplicate values explicitly

C. Using take() incorrectly on left and right children

D. Missing return statement in else branch

Solution

1. Step 1: Analyze unwrap() usage at function end

   root.unwrap() consumes root, but root is borrowed mutably earlier, causing move error.

2. Step 2: Correct approach for returning root

   Return root directly as Some(root) without unwrap to avoid move.

3. Final Answer:

   Calling unwrap() on root at the end consumes it, causing a move error -> Option A

4. Quick Check:

   unwrap() consumes Option, causes move error [OK]

Hint: Avoid unwrap() on Option when returning to prevent move errors [OK]

Common Mistakes:

• Ignoring move semantics of unwrap()
• Thinking take() is incorrect here
• Assuming missing return in else branch

5. You want to insert a list of values [20, 10, 30, 25, 35, 5] into an empty BST using Rust. After all insertions, which of the following represents the correct pre-order traversal output?

hard

A. [5, 10, 20, 25, 30, 35]

B. [10, 5, 20, 25, 30, 35]

C. [20, 30, 25, 35, 10, 5]

D. [20, 10, 5, 30, 25, 35]

Solution

1. Step 1: Insert values step-by-step

   Insert 20 as root; 10 left of 20; 30 right of 20; 25 left of 30; 35 right of 30; 5 left of 10.

2. Step 2: Perform pre-order traversal

   Pre-order visits root, left subtree, right subtree: 20, 10, 5, 30, 25, 35.

3. Final Answer:

   [20, 10, 5, 30, 25, 35] -> Option D

4. Quick Check:

   Pre-order = root-left-right [OK]

Hint: Pre-order = root, left subtree, then right subtree [OK]

Common Mistakes:

• Confusing pre-order with in-order traversal
• Inserting nodes in wrong positions
• Listing sorted values instead of traversal order