BST Search Operation in DSA Rust - Build from Scratch

BST Search Operation

📖 Scenario: You are building a simple phone book app that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to find if a contact exists by searching the BST.

🎯 Goal: Build a Rust program that creates a BST with given phone numbers, then searches for a specific phone number in the BST and prints if it is found or not.

📋 What You'll Learn

Create a BST node struct with integer phone number and optional left and right children

Insert given phone numbers into the BST

Search the BST for a given phone number using a recursive function

Print "Found" if the phone number exists, else print "Not Found"

💡 Why This Matters

🌍 Real World

BSTs are used in phone books, contact lists, and databases to quickly find entries by key.

💼 Career

Understanding BST search is fundamental for software engineers working with data structures and algorithms.

1

Create BST Node and Insert Phone Numbers

Create a struct called Node with a field phone of type i32, and two optional boxed children left and right of type Option>. Then create a function insert that takes a mutable reference to an Option> and an i32 phone number, and inserts the phone number into the BST following BST rules. Finally, create a mutable variable root of type Option> initialized to None. Insert these phone numbers into root in this order: 50, 30, 70, 20, 40, 60, 80.

DSA Rust

// Define Node struct and insert function
// Create mutable root variable
// Insert phone numbers 50, 30, 70, 20, 40, 60, 80 into root
// Your code here

Hint

Use Option> for children to allow recursive tree structure. Insert smaller phone numbers to the left, larger to the right.

2

Add Search Phone Number Variable

Add a variable called search_phone of type i32 and set it to 40. This will be the phone number we want to search in the BST.

DSA Rust

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

impl Node {
    fn new(phone: i32) -> Self {
        Node { phone, left: None, right: None }
    }
}

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

fn main() {
    let mut root: Option> = None;
    insert(&mut root, 50);
    insert(&mut root, 30);
    insert(&mut root, 70);
    insert(&mut root, 20);
    insert(&mut root, 40);
    insert(&mut root, 60);
    insert(&mut root, 80);
    // Your code here

Hint

Declare search_phone as an i32 variable and assign it the value 40.

3

Implement Recursive Search Function

Create a function called search that takes a reference to an Option> and an i32 phone number, and returns a bool. The function should recursively search the BST for the phone number. Return true if found, otherwise false. Use the BST property to decide to search left or right child.

DSA Rust

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

impl Node {
    fn new(phone: i32) -> Self {
        Node { phone, left: None, right: None }
    }
}

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

fn main() {
    let mut root: Option> = None;
    insert(&mut root, 50);
    insert(&mut root, 30);
    insert(&mut root, 70);
    insert(&mut root, 20);
    insert(&mut root, 40);
    insert(&mut root, 60);
    insert(&mut root, 80);
    let search_phone: i32 = 40;

    // Implement search function below
    // Your code here

Hint

Use pattern matching on root. If None, return false. If Some(node), compare phone with node.phone. Recurse left or right accordingly.

4

Print Search Result

Use println! to print "Found" if search(&root, search_phone) returns true, otherwise print "Not Found".

DSA Rust

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

impl Node {
    fn new(phone: i32) -> Self {
        Node { phone, left: None, right: None }
    }
}

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

fn search(root: &Option>, phone: i32) -> bool {
    match root {
        None => false,
        Some(node) => {
            if phone == node.phone {
                true
            } else if phone > = None;
    insert(&mut root, 50);
    insert(&mut root, 30);
    insert(&mut root, 70);
    insert(&mut root, 20);
    insert(&mut root, 40);
    insert(&mut root, 60);
    insert(&mut root, 80);
    let search_phone: i32 = 40;

    // Print "Found" if search returns true, else "Not Found"
    // Your code here

Hint

Use an if statement to check the result of search(&root, search_phone). Print "Found" if true, else "Not Found".

Practice

1. What does the search operation in a Binary Search Tree (BST) do?

easy

A. Counts the number of nodes in the BST

B. Inserts a new value into the BST

C. Deletes a value from the BST

D. Finds whether a given value exists in the BST

Solution

1. Step 1: Understand the purpose of BST search

   The search operation checks if a specific value is present in the BST by comparing values and moving left or right accordingly.

2. Step 2: Differentiate from other BST operations

   Insertion adds new nodes, deletion removes nodes, and counting nodes is a separate operation. Search only checks presence.

3. Final Answer:

   Finds whether a given value exists in the BST -> Option D

4. Quick Check:

   Search = Find value [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search counts nodes
• Assuming search modifies the tree

2. Which of the following is the correct Rust function signature for a BST search method that returns a boolean?

easy

A. fn search(&mut self, value: i32) -> i32

B. fn search(value: i32) -> bool

C. fn search(&self, value: i32) -> bool

D. fn search(&self, value: i32) -> Option<Node>

Solution

1. Step 1: Identify method receiver and return type

   Search should borrow the tree immutably (&self) and return true/false (bool) indicating presence.

2. Step 2: Check parameters and return correctness

   Value parameter is i32, and return type is bool. Mutable borrow or returning Node is incorrect for simple search.

3. Final Answer:

   fn search(&self, value: i32) -> bool -> Option C

4. Quick Check:

   Immutable borrow + bool return = fn search(&self, value: i32) -> bool [OK]

Hint: Search does not modify tree, so use &self and bool return [OK]

Common Mistakes:

• Using &mut self instead of &self
• Returning Node instead of bool
• Missing self parameter

3. Given this Rust code for BST search, what will be printed when searching for 7?

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

impl Node {
    fn search(&self, val: i32) -> bool {
        if val == self.value {
            true
        } else if val < self.value {
            match &self.left {
                Some(left_node) => left_node.search(val),
                None => false,
            }
        } else {
            match &self.right {
                Some(right_node) => right_node.search(val),
                None => false,
            }
        }
    }
}

fn main() {
    let root = Node {
        value: 5,
        left: Some(Box::new(Node { value: 3, left: None, right: None })),
        right: Some(Box::new(Node { value: 8, left: None, right: None })),
    };
    println!("{}", root.search(7));
}

medium

A. false

B. Runtime panic

C. Compilation error

D. true

Solution

1. Step 1: Trace search for value 7 starting at root 5

   7 > 5, so search right subtree with root 8.

2. Step 2: Search right subtree node with value 8 for 7

   7 < 8, so search left subtree of node 8, which is None, so returns false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   7 not found in tree = false [OK]

Hint: Follow BST rules: left < node < right [OK]

Common Mistakes:

• Assuming 7 is found because 8 exists
• Confusing left and right subtree directions
• Ignoring None case returns false

4. Identify the bug in this Rust BST search method:

fn search(&self, val: i32) -> bool {
    if val == self.value {
        true
    } else if val < self.value {
        self.left.as_ref().unwrap().search(val)
    } else {
        self.right.as_ref().unwrap().search(val)
    }
}

medium

A. Using unwrap() without checking if child exists can cause panic

B. Missing return keyword before recursive calls

C. Incorrect comparison operators used

D. Function should return Option<bool> instead of bool

Solution

1. Step 1: Analyze use of unwrap() on Option

   unwrap() assumes the Option is Some, but if child is None, it causes runtime panic.

2. Step 2: Understand safe alternative

   Should check if child exists using match or if let before calling search to avoid panic.

3. Final Answer:

   Using unwrap() without checking if child exists can cause panic -> Option A

4. Quick Check:

   unwrap() on None = panic [OK]

Hint: Never unwrap Option without checking Some first [OK]

Common Mistakes:

• Ignoring possibility of None causing panic
• Thinking unwrap() is safe always
• Confusing return types

5. You want to search for a value in a BST that may contain duplicate values on the right subtree. How should you modify the search operation to find if the value exists anywhere in the tree?

hard

A. Search left subtree if val <= node, else search right subtree

B. Search left subtree if val < node, else search both right subtree and current node for val

C. Search left subtree if val < node, else search right subtree and if not found, search left subtree again

D. Search both left and right subtrees regardless of comparison, then check current node

Solution

1. Step 1: Understand duplicates on right subtree

   Duplicates are stored on the right, so if val equals node value, we found it; else if val > node, search right subtree.

2. Step 2: Modify search to check current node and right subtree for duplicates

   If val equals node value, return true immediately. If val > node value, search right subtree. If val < node value, search left subtree.

3. Final Answer:

   Search left subtree if val < node, else search both right subtree and current node for val -> Option B

4. Quick Check:

   Duplicates on right: check current and right subtree [OK]

Hint: Check current node before right subtree for duplicates [OK]

Common Mistakes:

• Ignoring duplicates on right subtree
• Searching only one subtree without checking current node
• Searching left subtree unnecessarily for duplicates