261: Binary Search Tree — Insert and Search

Difficulty: 2 Level: Intermediate Pure functional BST — insert, search, and traverse without mutation, preserving the original tree on every operation.

The Problem This Solves

A binary search tree maintains sorted order automatically: every node's left subtree holds smaller values, every node's right subtree holds larger values. This ordering makes search O(log n) on balanced trees — far better than scanning a sorted list sequentially. The functional version never mutates. Every `insert` returns a new tree that shares structure with the original. The original tree remains unchanged — useful when you need snapshots, undo history, or concurrent reads without locks. This is persistence in the data structures sense: old versions persist alongside new ones. OCaml's GC handles persistence transparently — unchanged subtrees are shared by reference at no cost. In Rust, shared immutable substructure requires `Arc<T>` or explicit cloning. This example uses cloning to keep the code simple and readable; the cost of persistence is visible and explicit.

The Intuition

A BST is organised by a simple invariant: for any node with value `v`, everything in its left subtree is less than `v`, and everything in its right subtree is greater than `v`. Searching follows this invariant: if your target is less than the current node, go left; if greater, go right; if equal, you found it. Functional insert follows the same path down the tree, rebuilding each node along the path from root to insertion point. Nodes off the path are cloned unchanged. The result is a new tree that shares most of its structure with the old one — only the path from root to the new leaf is new. `Box<Bst<T>>` is required because `Bst<T>` contains itself. Without the `Box`, the compiler can't determine the size of `Bst<T>` at compile time — it would be infinite. `Box` allocates on the heap, making the size known (one pointer).

How It Works in Rust

#[derive(Debug, Clone, PartialEq)]
pub enum Bst<T> {
 Leaf,                              // empty tree / empty subtree
 Node(Box<Bst<T>>, T, Box<Bst<T>>), // left, value, right
}

impl<T: Ord + Clone> Bst<T> {
 // Functional insert: returns a new tree, original unchanged
 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(), // duplicate — no change
         },
     }
 }

 // Search: borrow the tree, O(log n) for balanced trees
 pub fn contains(&self, x: &T) -> bool {
     match self {
         Bst::Leaf => false,
         Bst::Node(left, val, right) => match x.cmp(val) {
             Ordering::Less    => left.contains(x),
             Ordering::Greater => right.contains(x),
             Ordering::Equal   => true,
         },
     }
 }

 // In-order traversal yields sorted sequence
 pub fn to_sorted_vec(&self) -> Vec<T> {
     match self {
         Bst::Leaf => vec![],
         Bst::Node(left, val, right) => {
             let mut result = left.to_sorted_vec();
             result.push(val.clone());
             result.extend(right.to_sorted_vec());
             result
         }
     }
 }
}

What This Unlocks

Persistent sorted sets — insert into a BST and keep the old version; compare two snapshots without copying the whole structure.
Sorted stream processing — insert arriving events by timestamp; in-order traversal gives them back sorted.
Foundation for balanced trees — once BST invariants are clear, extending to AVL or red-black trees is a well-defined next step.

Key Differences

Concept	OCaml	Rust
Recursive type	GC handles transparently	`Box<Bst<T>>` required for known size
Comparison	`<`, `>`, `=` work on all types	`Ord` trait bound explicit; `.cmp()` returns `Ordering`
Persistence cost	Unchanged subtrees shared via GC	Must `.clone()` each node on the insert path
Type parameters	`'a bst` — no constraints	`T: Ord + Clone` — bounds stated explicitly
Leaf node	`Leaf` constructor	`Bst::Leaf` — same pattern

/// Immutable Binary Search Tree — Insert, Membership, In-Order Traversal

#[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 new() -> Self {
        Bst::Leaf
    }

    /// Functional insert — returns a new tree, original unchanged.
    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(),
            },
        }
    }

    /// Membership check — borrows the tree, no allocation.
    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),
            },
        }
    }

    /// In-order traversal — returns sorted elements.
    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
            }
        }
    }

    pub fn from_iter(items: impl IntoIterator<Item = T>) -> Self {
        items
            .into_iter()
            .fold(Bst::new(), |tree, x| tree.insert(x))
    }
}

fn main() {
    let tree = Bst::build([5, 3, 7, 1, 4, 6, 8]);
    println!("inorder: {:?}", tree.inorder());
    println!("mem 4 = {}", tree.mem(&4));
    println!("mem 9 = {}", tree.mem(&9));

    // Persistence: original unchanged after insert
    let tree2 = tree.insert(10);
    println!("after insert 10: {:?}", tree2.inorder());
    println!("original still: {:?}", tree.inorder());
}

/* Output:
   inorder: [1, 3, 4, 5, 6, 7, 8]
   mem 4 = true
   mem 9 = false
   after insert 10: [1, 3, 4, 5, 6, 7, 8, 10]
   original still: [1, 3, 4, 5, 6, 7, 8]
*/

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"

📊 Detailed Comparison

OCaml vs Rust: Binary Search Tree — Insert and Search

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

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

1. Recursive types need Box: OCaml's GC handles recursive types transparently; Rust requires `Box` to make the type size known at compile time 2. 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 3. 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 4. Pattern matching is nearly identical: Both languages use exhaustive pattern matching on algebraic types — the syntax differs but the logic is the same 5. 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