105 Intermediate

105-trie — Trie (Prefix Tree)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "105-trie — Trie (Prefix Tree)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. A trie (from re-trie-val, sometimes called a prefix tree) stores strings with shared prefixes, enabling O(|key|) insertion and lookup regardless of how many strings are stored. Key difference from OCaml: 1. **Mutability**: Rust's `Trie` is mutable (insert mutates in place via `or_default()`); OCaml's trie is persistent.

Tutorial

The Problem

A trie (from re-trie-val, sometimes called a prefix tree) stores strings with shared prefixes, enabling O(|key|) insertion and lookup regardless of how many strings are stored. It is the data structure behind autocomplete, IP routing (longest-prefix match), spell checkers, and dictionary compression.

Unlike a hash map, a trie naturally supports prefix queries: "find all strings starting with foo" requires no additional structure.

🎯 Learning Outcomes

• Implement a trie using HashMap<char, Trie> for children

• Insert and search strings in O(|key|) time

• Perform prefix search to list all completions

• Compare HashMap-backed vs BTreeMap-backed trie (sorted output)

• Understand the memory trade-offs of trie vs hash map for string keys

Code Example

pub fn insert(&mut self, word: &str) {
    let mut node = self;
    for c in word.chars() {
        node = node.children.entry(c).or_default();
    }
    node.is_word = true;
}

module CMap = Map.Make(Char)
type trie = { is_word: bool; children: trie CMap.t }

let rec insert_go word i node =
  if i = String.length word then { node with is_word = true }
  else
    let c = word.[i] in
    let child = try CMap.find c node.children with Not_found -> empty in
    { node with children = CMap.add c (insert_go word (i+1) child) node.children }

Key Differences

Mutability: Rust's Trie is mutable (insert mutates in place via or_default()); OCaml's trie is persistent.

Children map type: Rust offers both HashMap<char, Trie> (O(1) lookup, unsorted) and BTreeMap<char, Trie> (sorted, like OCaml's Map.Make(Char)).

Default initialization: Rust's or_default() inserts a new empty Trie node if the character is not present; OCaml uses Not_found exception handling.

Memory layout: Rust's Box<Trie> inside HashMap requires heap allocation per node; OCaml's GC manages this automatically.

OCaml Approach

OCaml's trie uses a map for children:

module CharMap = Map.Make(Char)

type trie = { is_word: bool; children: trie CharMap.t }

let empty = { is_word = false; children = CharMap.empty }

let insert word trie =
  let rec go i node =
    if i = String.length word then { node with is_word = true }
    else
      let c = word.[i] in
      let child = try CharMap.find c node.children with Not_found -> empty in
      let new_child = go (i + 1) child in
      { node with children = CharMap.add c new_child node.children }
  in
  go 0 trie

OCaml's persistent map makes the trie persistent — each insert returns a new trie with structural sharing.

Full Source

#![allow(clippy::all)]
//! # Trie — Prefix Tree for Strings
//!
//! A trie stores strings with shared prefixes efficiently.
//! OCaml's `Map.Make(Char)` for children maps to Rust's `HashMap<char, Trie>`.

use std::collections::BTreeMap;
use std::collections::HashMap;

// ---------------------------------------------------------------------------
// Approach A: HashMap-based trie (idiomatic Rust)
// ---------------------------------------------------------------------------

#[derive(Debug, Default, Clone)]
pub struct Trie {
    is_word: bool,
    children: HashMap<char, Trie>,
}

impl Trie {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn insert(&mut self, word: &str) {
        let mut node = self;
        for c in word.chars() {
            node = node.children.entry(c).or_default();
        }
        node.is_word = true;
    }

    pub fn contains(&self, word: &str) -> bool {
        let mut node = self;
        for c in word.chars() {
            match node.children.get(&c) {
                Some(child) => node = child,
                None => return false,
            }
        }
        node.is_word
    }

    pub fn starts_with(&self, prefix: &str) -> bool {
        let mut node = self;
        for c in prefix.chars() {
            match node.children.get(&c) {
                Some(child) => node = child,
                None => return false,
            }
        }
        true
    }
}

// ---------------------------------------------------------------------------
// Approach B: Immutable trie (mirrors OCaml's functional style)
// ---------------------------------------------------------------------------

#[derive(Debug, Clone)]
pub struct FunctionalTrie {
    is_word: bool,
    children: BTreeMap<char, FunctionalTrie>,
}

impl FunctionalTrie {
    pub fn empty() -> Self {
        FunctionalTrie {
            is_word: false,
            children: BTreeMap::new(),
        }
    }

    pub fn insert(&self, word: &str) -> Self {
        self.insert_chars(&word.chars().collect::<Vec<_>>(), 0)
    }

    fn insert_chars(&self, chars: &[char], i: usize) -> Self {
        if i == chars.len() {
            FunctionalTrie {
                is_word: true,
                children: self.children.clone(),
            }
        } else {
            let c = chars[i];
            let child = self
                .children
                .get(&c)
                .cloned()
                .unwrap_or_else(FunctionalTrie::empty);
            let new_child = child.insert_chars(chars, i + 1);
            let mut new_children = self.children.clone();
            new_children.insert(c, new_child);
            FunctionalTrie {
                is_word: self.is_word,
                children: new_children,
            }
        }
    }

    pub fn contains(&self, word: &str) -> bool {
        let chars: Vec<char> = word.chars().collect();
        self.contains_chars(&chars, 0)
    }

    fn contains_chars(&self, chars: &[char], i: usize) -> bool {
        if i == chars.len() {
            self.is_word
        } else {
            match self.children.get(&chars[i]) {
                Some(child) => child.contains_chars(chars, i + 1),
                None => false,
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Approach C: Array-based trie (performance-oriented, ASCII only)
// ---------------------------------------------------------------------------

pub struct ArrayTrie {
    is_word: bool,
    children: [Option<Box<ArrayTrie>>; 26],
}

impl Default for ArrayTrie {
    fn default() -> Self {
        Self::new()
    }
}

impl ArrayTrie {
    pub fn new() -> Self {
        ArrayTrie {
            is_word: false,
            children: Default::default(),
        }
    }

    pub fn insert(&mut self, word: &str) {
        let mut node = self;
        for c in word.chars() {
            let idx = (c as u8 - b'a') as usize;
            node = node.children[idx].get_or_insert_with(|| Box::new(ArrayTrie::new()));
        }
        node.is_word = true;
    }

    pub fn contains(&self, word: &str) -> bool {
        let mut node = self;
        for c in word.chars() {
            let idx = (c as u8 - b'a') as usize;
            match &node.children[idx] {
                Some(child) => node = child,
                None => return false,
            }
        }
        node.is_word
    }
}

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

    #[test]
    fn test_insert_and_contains() {
        let mut t = Trie::new();
        for w in &["cat", "car", "card", "care", "dare"] {
            t.insert(w);
        }
        assert!(t.contains("cat"));
        assert!(!t.contains("ca"));
        assert!(t.contains("card"));
        assert!(t.contains("dare"));
        assert!(!t.contains("dog"));
    }

    #[test]
    fn test_starts_with() {
        let mut t = Trie::new();
        t.insert("hello");
        assert!(t.starts_with("hel"));
        assert!(!t.starts_with("world"));
    }

    #[test]
    fn test_functional_trie() {
        let t = FunctionalTrie::empty();
        let t = t.insert("cat").insert("car").insert("card");
        assert!(t.contains("cat"));
        assert!(t.contains("car"));
        assert!(!t.contains("ca"));
    }

    #[test]
    fn test_array_trie() {
        let mut t = ArrayTrie::new();
        t.insert("cat");
        t.insert("car");
        assert!(t.contains("cat"));
        assert!(t.contains("car"));
        assert!(!t.contains("ca"));
    }

    #[test]
    fn test_empty_string() {
        let mut t = Trie::new();
        t.insert("");
        assert!(t.contains(""));
    }
}

module CMap = Map.Make(Char)

type trie = { is_word: bool; children: trie CMap.t }

let empty = { is_word = false; children = CMap.empty }

let insert word trie =
  let rec go i node =
    if i = String.length word then { node with is_word = true }
    else
      let c = word.[i] in
      let child = try CMap.find c node.children with Not_found -> empty in
      { node with children = CMap.add c (go (i+1) child) node.children }
  in go 0 trie

let mem word trie =
  let rec go i node =
    if i = String.length word then node.is_word
    else match CMap.find_opt word.[i] node.children with
    | None -> false | Some child -> go (i+1) child
  in go 0 trie

let () =
  let t = List.fold_left (fun t w -> insert w t)
    empty ["cat";"car";"card";"care";"dare"] in
  List.iter (fun w ->
    Printf.printf "%s: %b\n" w (mem w t)
  ) ["cat";"ca";"card";"dare";"dog"]

✓ Tests Rust test suite

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

    #[test]
    fn test_insert_and_contains() {
        let mut t = Trie::new();
        for w in &["cat", "car", "card", "care", "dare"] {
            t.insert(w);
        }
        assert!(t.contains("cat"));
        assert!(!t.contains("ca"));
        assert!(t.contains("card"));
        assert!(t.contains("dare"));
        assert!(!t.contains("dog"));
    }

    #[test]
    fn test_starts_with() {
        let mut t = Trie::new();
        t.insert("hello");
        assert!(t.starts_with("hel"));
        assert!(!t.starts_with("world"));
    }

    #[test]
    fn test_functional_trie() {
        let t = FunctionalTrie::empty();
        let t = t.insert("cat").insert("car").insert("card");
        assert!(t.contains("cat"));
        assert!(t.contains("car"));
        assert!(!t.contains("ca"));
    }

    #[test]
    fn test_array_trie() {
        let mut t = ArrayTrie::new();
        t.insert("cat");
        t.insert("car");
        assert!(t.contains("cat"));
        assert!(t.contains("car"));
        assert!(!t.contains("ca"));
    }

    #[test]
    fn test_empty_string() {
        let mut t = Trie::new();
        t.insert("");
        assert!(t.contains(""));
    }
}

Deep Comparison

Comparison: Trie — OCaml vs Rust

Core Insight

OCaml's trie is naturally functional: Map.Make(Char) gives an immutable sorted map for children, and every insert returns a new trie (sharing unchanged subtrees via structural sharing). Rust's idiomatic trie is mutable — HashMap<char, Trie> with entry().or_default() for elegant insertion. The functional Rust version requires explicit .clone() where OCaml shares structure implicitly.

OCaml

module CMap = Map.Make(Char)
type trie = { is_word: bool; children: trie CMap.t }

let rec insert_go word i node =
  if i = String.length word then { node with is_word = true }
  else
    let c = word.[i] in
    let child = try CMap.find c node.children with Not_found -> empty in
    { node with children = CMap.add c (insert_go word (i+1) child) node.children }

Rust — Mutable HashMap

pub fn insert(&mut self, word: &str) {
    let mut node = self;
    for c in word.chars() {
        node = node.children.entry(c).or_default();
    }
    node.is_word = true;
}

Rust — Functional (BTreeMap)

pub fn insert(&self, word: &str) -> Self {
    // Clone children, recursively insert — mirrors OCaml but explicit cloning
}

Comparison Table

Aspect	OCaml	Rust (mutable)	Rust (functional)
Children map	`Map.Make(Char)` (tree)	`HashMap<char, Trie>`	`BTreeMap<char, Trie>`
Insert style	Returns new trie	Mutates in place	Returns new trie (clone)
Structural sharing	Automatic (GC)	N/A	Manual clone
Missing child	`Not_found` exception	`entry().or_default()`	`.unwrap_or_else(empty)`
Lookup	`CMap.find_opt`	`.get(&c)`	`.get(&c)`
Performance	O(k log 26) per op	O(k) amortized	O(k * clone_cost)

Learner Notes

• **entry().or_default()**: Rust's most elegant map pattern — creates the child node if missing, returns mutable ref

• Structural sharing: OCaml's GC enables cheap "copy" of unchanged subtrees; Rust must clone explicitly

• Array trie: [Option<Box<Trie>>; 26] gives O(1) child lookup vs O(log n) for tree maps — great for ASCII

• **Default trait**: Implementing Default for Trie enables or_default() — Rust's way to say "empty node"

• Recursive types: Both languages handle trie containing trie children — Rust needs no Box here because HashMap heap-allocates values

Exercises

Implement all_words(&self) -> Vec<String> that returns all strings stored in the trie in alphabetical order.

Write delete(&mut self, word: &str) -> bool that removes a word from the trie, cleaning up unused nodes.

Implement longest_common_prefix(words: &[&str]) -> String using a trie to find the longest prefix shared by all words.

Open Source Repos

functional-rust

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

Rust