BST Insert Operation in DSA Rust

Introduction

Syntax

Examples

Sample Program

Important Notes

Summary

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