Bird
Raised Fist0
DSA Rustprogramming~20 mins

BST Insert Operation in DSA Rust - Practice Problems & Challenges

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
BST Insert Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
What is the output after inserting 7 into the BST?

Consider the following Rust code that inserts a value into a Binary Search Tree (BST). What will be the printed BST in-order traversal after inserting the value 7?

DSA Rust
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn insert(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
        None => Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                let left = insert(node.borrow().left.clone(), val);
                node.borrow_mut().left = left;
            } else {
                let right = insert(node.borrow().right.clone(), val);
                node.borrow_mut().right = right;
            }
            Some(node)
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn main() {
    let mut root = Some(TreeNode::new(5));
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 6);
    root = insert(root, 10);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 7);

    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}
A[2, 3, 4, 5, 6, 8, 10, 7]
B[2, 3, 4, 5, 6, 7, 8, 10]
C[2, 3, 4, 5, 7, 6, 8, 10]
D[2, 3, 4, 5, 6, 8, 7, 10]
Attempts:
2 left
💡 Hint

Remember that in-order traversal of a BST prints values in sorted order.

❓ Predict Output
intermediate
2:00remaining
What is the output after inserting 1 into the BST?

Given the BST and insert function below, what is the in-order traversal output after inserting 1?

DSA Rust
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn insert(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
        None => Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                let left = insert(node.borrow().left.clone(), val);
                node.borrow_mut().left = left;
            } else {
                let right = insert(node.borrow().right.clone(), val);
                node.borrow_mut().right = right;
            }
            Some(node)
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn main() {
    let mut root = Some(TreeNode::new(5));
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 6);
    root = insert(root, 10);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 1);

    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}
A[1, 2, 3, 4, 5, 6, 10, 8]
B[2, 1, 3, 4, 5, 6, 8, 10]
C[1, 3, 2, 4, 5, 6, 8, 10]
D[1, 2, 3, 4, 5, 6, 8, 10]
Attempts:
2 left
💡 Hint

In-order traversal prints nodes in ascending order for BST.

🔧 Debug
advanced
2:00remaining
Why does this BST insert code cause a runtime error?

Examine the Rust code below for inserting into a BST. It compiles but causes a runtime error when inserting duplicate values. What is the cause?

DSA Rust
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn insert(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
        None => Some(TreeNode::new(val)),
        Some(node) => {
            if val <= node.borrow().val {
                let left = insert(node.borrow().left.clone(), val);
                node.borrow_mut().left = left;
            } else {
                let right = insert(node.borrow().right.clone(), val);
                node.borrow_mut().right = right;
            }
            Some(node)
        }
    }
}

fn main() {
    let mut root = Some(TreeNode::new(5));
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 3); // duplicate
}
AStack overflow due to missing base case in insert function
BBorrow checker error due to mutable and immutable borrow conflict
CInfinite recursion caused by inserting duplicates always to the left
DNull pointer dereference when accessing left child
Attempts:
2 left
💡 Hint

Think about what happens when the inserted value equals a node's value.

🧠 Conceptual
advanced
1:00remaining
Which property must hold true after inserting a value into a BST?

After inserting a new value into a Binary Search Tree (BST), which property must always be true?

AAll left subtree nodes have values less than the node, and all right subtree nodes have values greater than the node
BAll nodes in the tree have unique values
CThe tree is always balanced with equal nodes on left and right subtrees
DThe root node always contains the smallest value
Attempts:
2 left
💡 Hint

Recall the definition of a BST.

❓ Predict Output
expert
3:00remaining
What is the output of in-order traversal after these insertions?

Given the Rust BST insert code below, what is the in-order traversal output after inserting the values in this order: 15, 10, 20, 8, 12, 17, 25, 19?

DSA Rust
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn insert(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
        None => Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                let left = insert(node.borrow().left.clone(), val);
                node.borrow_mut().left = left;
            } else {
                let right = insert(node.borrow().right.clone(), val);
                node.borrow_mut().right = right;
            }
            Some(node)
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn main() {
    let mut root = None;
    let values = [15, 10, 20, 8, 12, 17, 25, 19];
    for &v in &values {
        root = insert(root, v);
    }
    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}
A[8, 10, 12, 15, 17, 19, 20, 25]
B[8, 10, 12, 15, 17, 20, 19, 25]
C[8, 10, 12, 15, 19, 17, 20, 25]
D[10, 8, 12, 15, 17, 19, 20, 25]
Attempts:
2 left
💡 Hint

In-order traversal of BST prints values in ascending order.

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard