BST Search - Rust DSA

Search a binary search tree for one present and one absent value.

Algorithm

Basic Implementation

basic.rs

use std::collections::VecDeque;
struct Node { value: i32, left: Option<Box<Node>>, right: Option<Box<Node>> }
impl Node {
    fn new(value: i32) -> Self { Self { value, left: None, right: None } }
    fn with(value: i32, left: Node, right: Node) -> Self {
        Self { value, left: Some(Box::new(left)), right: Some(Box::new(right)) }
    }
}
fn render(node: &Option<Box<Node>>) -> String {
    match node {
        None => "_".to_string(),
        Some(n) => {
            if n.left.is_none() && n.right.is_none() { n.value.to_string() }
            else { format!("{}({},{})", n.value, render(&n.left), render(&n.right)) }
        }
    }
}
fn sample_tree() -> Option<Box<Node>> {
    Some(Box::new(Node::with(4, Node::with(2, Node::new(1), Node::new(3)), Node::with(6, Node::new(5), Node::new(7)))))
}
fn list_string(values: &[i32]) -> String {
    format!("[{}]", values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "))
}
fn search(root: &Option<Box<Node>>, target: i32) -> bool { let mut node = root.as_ref(); while let Some(n) = node { if target == n.value { return true; } node = if target < n.value { n.left.as_ref() } else { n.right.as_ref() }; } false }
fn main() { let root = sample_tree(); println!("{}", if search(&root, 5) { "5 found" } else { "5 not found" }); println!("{}", if search(&root, 8) { "8 found" } else { "8 not found" }); }

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Complexity

Time: O(h) per search
Space: O(1) iterative

Implementation notes

Rust stores child links as Option<Box<Node>>, with None for an empty child and Some(Box<Node>) owning each subtree.
sample_tree() builds the searched tree with Node::with and Node::new, returning Option<Box<Node>> for 4(2(1,3),6(5,7)).
search(root: &Option<Box<Node>>, target: i32) -> bool borrows the tree read-only and returns a boolean result, not a node or index.
The cursor starts as let mut node = root.as_ref(), converting Option<Box<Node>> into Option<&Box<Node>> without moving ownership.
while let Some(n) = node reads the current node. Equality returns true; otherwise the branch expression reborrows either n.left.as_ref() or n.right.as_ref().
The trace searches 5 by visiting 4 and branching right, visiting 6 and branching left, then matching at 5.
Searching 8 visits 4, 6, and 7, branches right each time, then reaches a null cursor and returns false. This lesson has no separate imbalance contrast; the miss path is the visible boundary in the trace.
main prints display-formatted string literals selected by the boolean return: 5 found and 8 not found.

search path A comparison chooses one subtree at each step, so whole branches are skipped.