BST Insert Operation in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a tree where each node has at most two children. The left child's value is less than the parent node's value, and the right child's value is greater. This helps in fast searching, inserting, and deleting.

beginner

What is the main rule to follow when inserting a new value in a BST?

Compare the new value with the current node's value. If smaller, go to the left child; if larger, go to the right child. Repeat until you find an empty spot to insert the new node.

intermediate

In Rust, what is the common way to represent a BST node with optional children?

Use an enum Option for left and right children. Option means the child can be None (empty) or Some(Box<Node>) holding a node. Box is used to store data on the heap.

beginner

Why do we use recursion in BST insert operation?

Recursion helps to move down the tree easily by calling the insert function on left or right child until the correct empty spot is found for the new value.

intermediate

What happens if you try to insert a value already present in the BST?

Usually, BST insert ignores duplicates or handles them by a rule (like inserting to the right). In simple BST insert, duplicates are not inserted again to keep unique values.

What is the first step when inserting a new value into a BST?

A Always insert to the right child

B Insert the value at the root without comparison

C Compare the new value with the root node's value

D Always insert to the left child

You start by comparing the new value with the root node to decide whether to go left or right.

In a BST, where do values smaller than a node go?

A To the left child

B To the right child

C At the same node

D They are not allowed

Smaller values go to the left child in a BST.

What Rust type is commonly used to represent a child node that might be empty?

A Vec<Node>

B Option<Box<Node>>

C Node

D Box<Option<Node>>

Option> means the child can be None or Some node stored on the heap.

What happens if you insert a duplicate value in a simple BST insert operation?

A It replaces the existing node

B It is inserted to the left child

C It is inserted to the right child

D It is ignored and not inserted

Simple BST insert usually ignores duplicates to keep unique values.

Why is recursion useful in BST insert?

A It helps to find the correct spot by moving down the tree

B It makes the code run faster

C It avoids using memory

D It prevents duplicates

Recursion helps to move down the tree until the right empty spot is found.

Explain how the BST insert operation works step-by-step.

Think about walking down the tree comparing values.

Describe how you would represent a BST node in Rust and why.

Focus on how Rust handles optional and recursive data.

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