BST Insert Operation in DSA Rust - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value in a Binary Search Tree changes as the tree grows.

How does the number of steps needed to insert a new value grow with the size of the tree?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

fn insert(root: &mut Option>, val: i32) {
    match root {
        None => *root = Some(Box::new(Node { value: val, left: None, right: None })),
        Some(node) => {
            if val < node.value {
                insert(&mut node.left, val);
            } else {
                insert(&mut node.right, val);
            }
        }
    }
}
    

This code inserts a value into a Binary Search Tree by moving left or right until it finds the right spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down the tree nodes.
• How many times: At most once per tree level, until a leaf spot is found.

How Execution Grows With Input

Each insert moves down one level in the tree, so the steps grow with the tree's height.

Input Size (n)	Approx. Operations
10	Up to 4 steps (if tree is balanced)
100	Up to 7 steps (if tree is balanced)
1000	Up to 10 steps (if tree is balanced)

Pattern observation: In a balanced tree, steps grow slowly (logarithmically) as the tree grows.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the time to insert depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Insertion always takes the same time regardless of tree shape."

[OK] Correct: If the tree is unbalanced and looks like a linked list, insertion can take much longer because you must go through many nodes.

Interview Connect

Understanding how tree shape affects insert time helps you explain trade-offs and choose the right data structure in real problems.

Self-Check

"What if we kept the tree balanced after each insert? How would the time complexity change?"

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