261 Intermediate

Binary Search Tree — Insert and Search

Trees

Tutorial Video

Text description (accessibility)

This video demonstrates the "Binary Search Tree — Insert and Search" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Trees. Implement an immutable binary search tree with functional insert, membership check, and in-order traversal. Key difference from OCaml: 1. **Heap allocation:** OCaml GC handles it implicitly; Rust needs `Box` for recursive types

Tutorial

The Problem

Implement an immutable binary search tree with functional insert, membership check, and in-order traversal. Each insert returns a new tree while the original remains unchanged (persistence).

🎯 Learning Outcomes

• Using enum with Box for recursive data structures in Rust

• Understanding persistent data structures through clone-on-write semantics

• Translating OCaml's pattern matching on algebraic types to Rust's match

• Using Ord trait for generic comparison instead of OCaml's structural equality

🦀 The Rust Way

Rust requires Box<T> for recursive enum variants since the compiler needs to know the size at compile time. The Ord trait replaces OCaml's polymorphic comparison. Cloning subtrees is explicit, making the cost of persistence visible.

Code Example

#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
    Leaf,
    Node(Box<Bst<T>>, T, Box<Bst<T>>),
}

impl<T: Ord + Clone> Bst<T> {
    pub fn insert(&self, x: T) -> Self {
        match self {
            Bst::Leaf => Bst::Node(Box::new(Bst::Leaf), x, Box::new(Bst::Leaf)),
            Bst::Node(left, val, right) => match x.cmp(val) {
                Ordering::Less => Bst::Node(Box::new(left.insert(x)), val.clone(), right.clone()),
                Ordering::Greater => Bst::Node(left.clone(), val.clone(), Box::new(right.insert(x))),
                Ordering::Equal => self.clone(),
            },
        }
    }

    pub fn mem(&self, x: &T) -> bool {
        match self {
            Bst::Leaf => false,
            Bst::Node(left, val, right) => match x.cmp(val) {
                Ordering::Equal => true,
                Ordering::Less => left.mem(x),
                Ordering::Greater => right.mem(x),
            },
        }
    }
}

type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, v, r) ->
    if x < v then Node (insert x l, v, r)
    else if x > v then Node (l, v, insert x r)
    else Node (l, v, r)

let rec mem x = function
  | Leaf -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then mem x l
    else mem x r

Key Differences

Heap allocation: OCaml GC handles it implicitly; Rust needs Box for recursive types

Comparison: OCaml uses built-in <, >, = for all types; Rust requires Ord trait bound

Persistence cost: OCaml shares unchanged subtrees via GC; Rust must .clone() explicitly

Type parameters: OCaml uses 'a with no constraints; Rust needs T: Ord + Clone

OCaml Approach

OCaml defines a polymorphic BST with type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst. Structural equality and comparison operators work automatically for all types. The recursive structure is naturally heap-allocated by the GC.

Full Source

#![allow(clippy::all)]
//! Immutable Binary Search Tree
//!
//! OCaml uses `type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst`.
//! Rust uses `enum Bst<T>` with `Box` for heap allocation of recursive variants.
//! Both languages naturally express immutable, persistent data structures.

//! A persistent (immutable) binary search tree.
//! Each insert creates a new tree sharing unchanged subtrees with the original.
#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
    Leaf,
    Node(Box<Bst<T>>, T, Box<Bst<T>>),
}

impl<T: Ord + Clone> Bst<T> {
    /// Creates an empty tree.
    pub fn new() -> Self {
        Bst::Leaf
    }

    /// Inserts a value, returning a new tree.
    /// Duplicates are ignored (set semantics).
    ///
    /// OCaml: `let rec insert x = function | Leaf -> Node(Leaf, x, Leaf) | ...`
    /// Rust must use Box for recursive heap allocation.
    pub fn insert(&self, x: T) -> Self {
        match self {
            Bst::Leaf => Bst::Node(Box::new(Bst::Leaf), x, Box::new(Bst::Leaf)),
            Bst::Node(left, val, right) => match x.cmp(val) {
                std::cmp::Ordering::Less => {
                    Bst::Node(Box::new(left.insert(x)), val.clone(), right.clone())
                }
                std::cmp::Ordering::Greater => {
                    Bst::Node(left.clone(), val.clone(), Box::new(right.insert(x)))
                }
                std::cmp::Ordering::Equal => self.clone(),
            },
        }
    }

    /// Checks membership in the tree.
    ///
    /// OCaml: `let rec mem x = function | Leaf -> false | Node(l,v,r) -> ...`
    /// Rust borrows `&self` — no allocation needed for lookup.
    pub fn mem(&self, x: &T) -> bool {
        match self {
            Bst::Leaf => false,
            Bst::Node(left, val, right) => match x.cmp(val) {
                std::cmp::Ordering::Equal => true,
                std::cmp::Ordering::Less => left.mem(x),
                std::cmp::Ordering::Greater => right.mem(x),
            },
        }
    }

    /// Returns elements in sorted order via in-order traversal.
    ///
    /// OCaml: `let rec inorder = function | Leaf -> [] | Node(l,v,r) -> inorder l @ [v] @ inorder r`
    /// Rust collects into a Vec, which owns the values.
    pub fn inorder(&self) -> Vec<T> {
        match self {
            Bst::Leaf => vec![],
            Bst::Node(left, val, right) => {
                let mut result = left.inorder();
                result.push(val.clone());
                result.extend(right.inorder());
                result
            }
        }
    }

    /// Functional construction: builds a tree from an iterator.
    /// Mirrors OCaml's `List.fold_left (fun t x -> insert x t) Leaf items`.
    pub fn build(items: impl IntoIterator<Item = T>) -> Self {
        items.into_iter().fold(Bst::new(), |tree, x| tree.insert(x))
    }
}

impl<T: Ord + Clone> Default for Bst<T> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_tree() {
        let tree: Bst<i32> = Bst::new();
        assert_eq!(tree.inorder(), Vec::<i32>::new());
        assert!(!tree.mem(&1));
    }

    #[test]
    fn test_single_element() {
        let tree = Bst::new().insert(42);
        assert_eq!(tree.inorder(), vec![42]);
        assert!(tree.mem(&42));
        assert!(!tree.mem(&0));
    }

    #[test]
    fn test_multiple_elements_sorted() {
        let tree = Bst::build([5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(tree.inorder(), vec![1, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_membership() {
        let tree = Bst::build([5, 3, 7, 1, 4, 6, 8]);
        assert!(tree.mem(&4));
        assert!(tree.mem(&5));
        assert!(tree.mem(&8));
        assert!(!tree.mem(&9));
        assert!(!tree.mem(&0));
        assert!(!tree.mem(&2));
    }

    #[test]
    fn test_duplicate_insert() {
        let tree = Bst::build([3, 1, 3, 2, 1]);
        assert_eq!(tree.inorder(), vec![1, 2, 3]);
    }

    #[test]
    fn test_persistence() {
        // Inserting into a tree doesn't modify the original
        let tree1 = Bst::build([5, 3, 7]);
        let tree2 = tree1.insert(1);
        assert!(!tree1.mem(&1));
        assert!(tree2.mem(&1));
    }
}

type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, v, r) ->
    if x < v then Node (insert x l, v, r)
    else if x > v then Node (l, v, insert x r)
    else Node (l, v, r)

let rec mem x = function
  | Leaf -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then mem x l
    else mem x r

let rec inorder = function
  | Leaf -> []
  | Node (l, v, r) -> inorder l @ [v] @ inorder r

let () =
  let tree = List.fold_left (fun t x -> insert x t) Leaf [5;3;7;1;4;6;8] in
  assert (inorder tree = [1;3;4;5;6;7;8]);
  assert (mem 4 tree = true);
  assert (mem 9 tree = false);
  assert (inorder Leaf = []);
  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_tree() {
        let tree: Bst<i32> = Bst::new();
        assert_eq!(tree.inorder(), Vec::<i32>::new());
        assert!(!tree.mem(&1));
    }

    #[test]
    fn test_single_element() {
        let tree = Bst::new().insert(42);
        assert_eq!(tree.inorder(), vec![42]);
        assert!(tree.mem(&42));
        assert!(!tree.mem(&0));
    }

    #[test]
    fn test_multiple_elements_sorted() {
        let tree = Bst::build([5, 3, 7, 1, 4, 6, 8]);
        assert_eq!(tree.inorder(), vec![1, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_membership() {
        let tree = Bst::build([5, 3, 7, 1, 4, 6, 8]);
        assert!(tree.mem(&4));
        assert!(tree.mem(&5));
        assert!(tree.mem(&8));
        assert!(!tree.mem(&9));
        assert!(!tree.mem(&0));
        assert!(!tree.mem(&2));
    }

    #[test]
    fn test_duplicate_insert() {
        let tree = Bst::build([3, 1, 3, 2, 1]);
        assert_eq!(tree.inorder(), vec![1, 2, 3]);
    }

    #[test]
    fn test_persistence() {
        // Inserting into a tree doesn't modify the original
        let tree1 = Bst::build([5, 3, 7]);
        let tree2 = tree1.insert(1);
        assert!(!tree1.mem(&1));
        assert!(tree2.mem(&1));
    }
}

Deep Comparison

OCaml vs Rust: Binary Search Tree — Insert and Search

Side-by-Side Code

OCaml

type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, v, r) ->
    if x < v then Node (insert x l, v, r)
    else if x > v then Node (l, v, insert x r)
    else Node (l, v, r)

let rec mem x = function
  | Leaf -> false
  | Node (l, v, r) ->
    if x = v then true
    else if x < v then mem x l
    else mem x r

Rust (idiomatic)

#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
    Leaf,
    Node(Box<Bst<T>>, T, Box<Bst<T>>),
}

impl<T: Ord + Clone> Bst<T> {
    pub fn insert(&self, x: T) -> Self {
        match self {
            Bst::Leaf => Bst::Node(Box::new(Bst::Leaf), x, Box::new(Bst::Leaf)),
            Bst::Node(left, val, right) => match x.cmp(val) {
                Ordering::Less => Bst::Node(Box::new(left.insert(x)), val.clone(), right.clone()),
                Ordering::Greater => Bst::Node(left.clone(), val.clone(), Box::new(right.insert(x))),
                Ordering::Equal => self.clone(),
            },
        }
    }

    pub fn mem(&self, x: &T) -> bool {
        match self {
            Bst::Leaf => false,
            Bst::Node(left, val, right) => match x.cmp(val) {
                Ordering::Equal => true,
                Ordering::Less => left.mem(x),
                Ordering::Greater => right.mem(x),
            },
        }
    }
}

Type Signatures

Concept	OCaml	Rust
Tree type	`'a bst`	`Bst<T>`
Insert	`val insert : 'a -> 'a bst -> 'a bst`	`fn insert(&self, x: T) -> Self`
Membership	`val mem : 'a -> 'a bst -> bool`	`fn mem(&self, x: &T) -> bool`
In-order	`val inorder : 'a bst -> 'a list`	`fn inorder(&self) -> Vec<T>`
Empty tree	`Leaf`	`Bst::Leaf`

Key Insights

Recursive types need Box: OCaml's GC handles recursive types transparently; Rust requires Box to make the type size known at compile time

Trait bounds make costs explicit: OCaml's polymorphic comparison is free but can fail at runtime for incomparable types; Rust's T: Ord guarantees comparability at compile time

Clone reveals persistence cost: When inserting, unchanged subtrees must be cloned. In OCaml, the GC shares references automatically; in Rust, .clone() makes this cost visible

Pattern matching is nearly identical: Both languages use exhaustive pattern matching on algebraic types — the syntax differs but the logic is the same

Method vs function style: OCaml uses standalone recursive functions; Rust idiomatically uses impl blocks with &self methods

When to Use Each Style

Use persistent BST when: you need undo/redo, versioned data, or concurrent readers without locks Use mutable BST when: performance is critical and you don't need to preserve old versions

Exercises

Implement delete for the BST: remove an arbitrary node while maintaining the BST invariant (use in-order successor replacement for nodes with two children).

Write an is_valid_bst checker that verifies the BST property holds for every node (not just locally), using range constraints propagated through the recursion.

Implement a balanced BST construction from a sorted Vec<T> using divide-and-conquer (select the median as root), and verify the resulting tree has O(log n) height.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust