BST Search Operation in DSA Rust

Mental Model

A binary search tree lets you find a value by comparing and moving left or right, skipping many values at once.

Analogy: Like looking for a name in a phone book by opening to the middle and deciding to go left or right depending on the name's order.

      5
     / \
    3   7
   / \   \
  2   4   8
↑ (start at root)

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, search for value 4

Goal: Find if value 4 exists in the BST and show the path taken

Step 1: Start at root node with value 5

5 [curr->5] -> 3 -> 7 -> 2 -> 4 -> 8

Why: We always start searching from the root of the BST

Step 2: Compare 4 with 5, move left because 4 < 5

5 -> 3 [curr->3] -> 7 -> 2 -> 4 -> 8

Why: In BST, smaller values are on the left subtree

Step 3: Compare 4 with 3, move right because 4 > 3

5 -> 3 -> 4 [curr->4] -> 7 -> 2 -> 8

Why: In BST, larger values are on the right subtree

Step 4: Found node with value 4, stop search

5 -> 3 -> 4 [found]

Why: We found the value we were searching for

Result:

5 -> 3 -> 4 found

Annotated Code

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 bst_search(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> bool {
    let mut current = root;
    while let Some(node_rc) = current {
        let node = node_rc.borrow();
        if node.val == target {
            return true; // found the target
        } else if target < node.val {
            current = node.left.clone(); // go left
        } else {
            current = node.right.clone(); // go right
        }
    }
    false // not found
}

fn main() {
    // Build BST manually: 5
    //                   /   \
    //                  3     7
    //                 / \     \
    //                2   4     8
    let root = TreeNode::new(5);
    {
        let mut r = root.borrow_mut();
        r.left = Some(TreeNode::new(3));
        r.right = Some(TreeNode::new(7));
    }
    {
        let left = root.borrow().left.clone().unwrap();
        let mut l = left.borrow_mut();
        l.left = Some(TreeNode::new(2));
        l.right = Some(TreeNode::new(4));
    }
    {
        let right = root.borrow().right.clone().unwrap();
        let mut r = right.borrow_mut();
        r.right = Some(TreeNode::new(8));
    }

    let target = 4;
    let found = bst_search(Some(root), target);
    println!("{} found: {}", target, found);
}

while let Some(node_rc) = current {

loop through nodes until we reach null

if node.val == target {

check if current node is the target

current = node.left.clone();

move left if target is smaller

current = node.right.clone();

move right if target is larger

Output

4 found: true

Complexity Analysis

Time: O(h) where h is the height of the tree because we move down one level each step

Space: O(1) because we only keep track of one current node pointer

vs Alternative: Compared to searching an unsorted tree or list which is O(n), BST search is faster if tree is balanced

Edge Cases

Empty tree

Returns false immediately because root is None

DSA Rust

while let Some(node_rc) = current {

Target not in tree

Returns false after reaching a null child

DSA Rust

while let Some(node_rc) = current {

Target is root value

Returns true immediately at first comparison

DSA Rust

if node.val == target {

When to Use This Pattern

When you need to quickly find a value in a sorted tree structure, use BST search because it skips half the tree at each step.

Common Mistakes

Mistake: Not moving left or right correctly based on comparison
Fix: Compare target with current node value and move left if smaller, right if larger

Summary

Searches for a value in a binary search tree by moving left or right based on comparisons.

Use when you have a BST and want to find if a value exists efficiently.

The key is to compare and decide direction at each node to skip large parts of the tree.

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