BST Insert Operation in DSA Rust - Execution Trace

Concept Flow - BST Insert Operation

Create new node

↓

Start at root

↓

Compare new value with current node

↓

Go left

↓

Is child null?

No→Move to child node

Yes↓

Insert new node here

↓

Done

Insert starts at root, compares values, moves left or right until a null child is found, then inserts the new node there.

Execution Sample

DSA Rust

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

This recursive function inserts a value into the BST by traversing left or right until it finds the correct empty spot.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Create new node with val=25	N/A	N/A	New node created: 25	30 / ? ?
2	Start at root	30	25 < 30? Yes	Move to left child	30 / ? ?
3	At node 20	20	25 < 20? No	Move to right child	30 / 20 ?
4	At node None (right child of 20)	None	N/A	Insert new node 25 here	30 / 20 ∅ \ 25
5	Update parent's right pointer	20	N/A	20.right → 25	30 / 20 ∅ \ 25
6	Insertion complete	N/A	N/A	No pointer changes	30 / \ 20 ∅ \ 25

💡 Inserted new node at null child position; recursion unwinds.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current_node	30	20	None	None	None
comparison	N/A	25 < 30: Yes	25 < 20: No	N/A	N/A
pointer_change	None	Moved to left child	Moved to right child	Inserted node 25	No change

Key Moments - 3 Insights

Why do we insert the new node when the current child pointer is None?

Because a None child means there is no node there, so it's the correct place to insert the new node. See execution_table step 4 where insertion happens at None.

Why do we move left if the new value is smaller, and right if larger or equal?

BST property requires left children to be smaller and right children to be larger or equal. This is shown in execution_table steps 2 and 3 where comparisons decide direction.

What happens if the tree is empty at the start?

The new node becomes the root. This is handled in the execution_sample code when root.is_none().

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 3?

A 30

B 20

C None

D 25

💡 Hint

Check the 'Current Node' column at step 3 in execution_table.

At which step does the insertion of the new node happen?

A Step 2

B Step 3

C Step 4

D Step 6

💡 Hint

Look for 'Insert new node' in the 'Operation' column in execution_table.

If the new value was 15 instead of 25, which direction would the insertion go at step 3?

A Left

B Right

C Stay at current node

D Insert at root

💡 Hint

Refer to the comparison logic in execution_table steps 2 and 3.

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- If smaller, go left; if larger or equal, go right
- Repeat until a null child is found
- Insert new node at null child
- Maintains BST property

Full Transcript

The BST insert operation begins by creating a new node with the value to insert. Starting at the root, the algorithm compares the new value with the current node's value. If the new value is smaller, it moves to the left child; if larger or equal, it moves to the right child. This traversal continues until it finds a null child pointer, which means the correct spot to insert the new node. The new node is then linked as that child, maintaining the binary search tree property. If the tree is empty, the new node becomes the root. This process is recursive and ensures the tree remains sorted.

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