Tries (Prefix Trees)

A Trie (pronounced "try") is a tree-like data structure used to store strings where each node represents a character. Tries are particularly efficient for prefix-based operations like autocomplete, spell checking, and IP routing.

Key properties:

• Each node represents a character or prefix
• Root represents empty string
• Paths from root to nodes represent prefixes
• Common prefixes share nodes (memory efficient)
• O(k) lookup where k is key length

The Rust perspective:

• HashMap-based children for flexibility
• Array-based children for ASCII-only (faster)
• Ownership of strings vs. references
• Generic implementations for different key types

use std::collections::HashMap;

/// Basic trie node
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
}

Appropriate use cases:

1. Autocomplete and search suggestions
2. Spell checkers and word validation
3. IP routing tables (CIDR matching)
4. Phone directory lookups
5. Dictionary implementations
6. Prefix matching and longest prefix match

When to use alternatives:

1. Exact key lookup only → HashMap
2. Sorted iteration needed → BTreeMap
3. Memory constrained → Radix tree
4. Very long keys → Hash-based structures

A complete trie implementation for string storage.

use std::collections::HashMap;

/// Trie node with HashMap-based children
#[derive(Debug, Default)]
pub struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
    /// Optional: store count of words with this prefix
    prefix_count: usize,
    /// Optional: store the complete word at terminal nodes
    word: Option<String>,
}

/// String trie data structure
#[derive(Debug, Default)]
pub struct Trie {
    root: TrieNode,
    word_count: usize,
}

impl Trie {
    /// Create a new empty trie
    pub fn new() -> Self {
        Self::default()
    }

    /// Insert a word into the trie
    pub fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;

        for ch in word.chars() {
            node.prefix_count += 1;
            node = node.children.entry(ch).or_default();
        }

        if !node.is_end {
            node.is_end = true;
            node.word = Some(word.to_string());
            self.word_count += 1;
        }
        node.prefix_count += 1;
    }

    /// Check if word exists in trie
    pub fn contains(&self, word: &str) -> bool {
        self.find_node(word)
            .map_or(false, |node| node.is_end)
    }

    /// Check if any word starts with prefix
    pub fn starts_with(&self, prefix: &str) -> bool {
        self.find_node(prefix).is_some()
    }

    /// Count words with given prefix
    pub fn count_prefix(&self, prefix: &str) -> usize {
        self.find_node(prefix)
            .map_or(0, |node| node.prefix_count)
    }

    /// Get all words with given prefix
    pub fn words_with_prefix(&self, prefix: &str) -> Vec<String> {
        let mut results = Vec::new();

        if let Some(node) = self.find_node(prefix) {
            self.collect_words(node, &mut results);
        }

        results
    }

    /// Remove a word from the trie
    pub fn remove(&mut self, word: &str) -> bool {
        if !self.contains(word) {
            return false;
        }

        self.remove_recursive(&mut self.root, word, 0);
        self.word_count -= 1;
        true
    }

    /// Get total number of words
    pub fn len(&self) -> usize {
        self.word_count
    }

    /// Check if trie is empty
    pub fn is_empty(&self) -> bool {
        self.word_count == 0
    }

    /// Get all words in the trie
    pub fn all_words(&self) -> Vec<String> {
        let mut results = Vec::new();
        self.collect_words(&self.root, &mut results);
        results
    }

    /// Find longest common prefix of all words
    pub fn longest_common_prefix(&self) -> String {
        let mut prefix = String::new();
        let mut node = &self.root;

        loop {
            // If node has multiple children or is end of word, stop
            if node.children.len() != 1 || node.is_end {
                break;
            }

            // Get the only child
            let (&ch, next_node) = node.children.iter().next().unwrap();
            prefix.push(ch);
            node = next_node;
        }

        prefix
    }

    // Helper: Find node for given key
    fn find_node(&self, key: &str) -> Option<&TrieNode> {
        let mut node = &self.root;

        for ch in key.chars() {
            node = node.children.get(&ch)?;
        }

        Some(node)
    }

    // Helper: Collect all words from node
    fn collect_words(&self, node: &TrieNode, results: &mut Vec<String>) {
        if let Some(ref word) = node.word {
            results.push(word.clone());
        }

        for child in node.children.values() {
            self.collect_words(child, results);
        }
    }

    // Helper: Remove word recursively
    fn remove_recursive(&mut self, node: &mut TrieNode, word: &str, depth: usize) -> bool {
        let chars: Vec<char> = word.chars().collect();

        if depth == chars.len() {
            if node.is_end {
                node.is_end = false;
                node.word = None;
                node.prefix_count -= 1;
                return node.children.is_empty();
            }
            return false;
        }

        let ch = chars[depth];
        if let Some(child) = node.children.get_mut(&ch) {
            if self.remove_recursive(child, word, depth + 1) {
                node.children.remove(&ch);
            }
            node.prefix_count -= 1;
            return !node.is_end && node.children.is_empty();
        }

        false
    }
}

fn main() {
    let mut trie = Trie::new();

    // Insert words
    let words = ["apple", "application", "apply", "apt", "banana", "band", "bandana"];
    for word in &words {
        trie.insert(word);
    }

    println!("Total words: {}", trie.len());

    // Search
    println!("\nSearch results:");
    println!("  'apple' exists: {}", trie.contains("apple"));
    println!("  'app' exists: {}", trie.contains("app"));
    println!("  starts with 'app': {}", trie.starts_with("app"));

    // Prefix operations
    println!("\nPrefix 'app':");
    println!("  Count: {}", trie.count_prefix("app"));
    println!("  Words: {:?}", trie.words_with_prefix("app"));

    println!("\nPrefix 'ban':");
    println!("  Words: {:?}", trie.words_with_prefix("ban"));

    // All words
    println!("\nAll words: {:?}", trie.all_words());

    // Longest common prefix
    let mut trie2 = Trie::new();
    trie2.insert("flower");
    trie2.insert("flow");
    trie2.insert("flight");
    println!("\nLongest common prefix of [flower, flow, flight]: '{}'",
             trie2.longest_common_prefix());

    // Remove
    println!("\nRemoving 'apple': {}", trie.remove("apple"));
    println!("'apple' exists after removal: {}", trie.contains("apple"));
    println!("Words with prefix 'app': {:?}", trie.words_with_prefix("app"));
}

A complete autocomplete implementation with ranking.

use std::collections::HashMap;
use std::cmp::Reverse;

/// Autocomplete entry with frequency
#[derive(Debug, Clone)]
pub struct AutocompleteEntry {
    pub word: String,
    pub frequency: u64,
}

/// Trie node for autocomplete
#[derive(Debug, Default)]
struct AutocompleteNode {
    children: HashMap<char, AutocompleteNode>,
    entry: Option<AutocompleteEntry>,
    /// Top suggestions at this node (cached for performance)
    top_suggestions: Vec<AutocompleteEntry>,
}

/// Autocomplete system with frequency-based ranking
pub struct Autocomplete {
    root: AutocompleteNode,
    max_suggestions: usize,
}

impl Autocomplete {
    pub fn new(max_suggestions: usize) -> Self {
        Self {
            root: AutocompleteNode::default(),
            max_suggestions,
        }
    }

    /// Add a word or increment its frequency
    pub fn add(&mut self, word: &str) {
        self.add_with_frequency(word, 1);
    }

    /// Add a word with specific frequency
    pub fn add_with_frequency(&mut self, word: &str, frequency: u64) {
        let mut node = &mut self.root;

        for ch in word.chars() {
            node = node.children.entry(ch).or_default();
        }

        match &mut node.entry {
            Some(entry) => entry.frequency += frequency,
            None => {
                node.entry = Some(AutocompleteEntry {
                    word: word.to_string(),
                    frequency,
                });
            }
        }

        // Rebuild suggestions along the path
        self.rebuild_suggestions(word);
    }

    /// Get autocomplete suggestions for prefix
    pub fn suggest(&self, prefix: &str) -> Vec<AutocompleteEntry> {
        if let Some(node) = self.find_node(prefix) {
            node.top_suggestions.clone()
        } else {
            Vec::new()
        }
    }

    /// Record a selection (boosts frequency)
    pub fn record_selection(&mut self, word: &str) {
        self.add(word);
    }

    /// Get suggestions with custom limit
    pub fn suggest_n(&self, prefix: &str, n: usize) -> Vec<AutocompleteEntry> {
        self.suggest(prefix).into_iter().take(n).collect()
    }

    fn find_node(&self, prefix: &str) -> Option<&AutocompleteNode> {
        let mut node = &self.root;
        for ch in prefix.chars() {
            node = node.children.get(&ch)?;
        }
        Some(node)
    }

    fn find_node_mut(&mut self, prefix: &str) -> Option<&mut AutocompleteNode> {
        let mut node = &mut self.root;
        for ch in prefix.chars() {
            node = node.children.get_mut(&ch)?;
        }
        Some(node)
    }

    fn rebuild_suggestions(&mut self, word: &str) {
        // Collect all entries from node
        fn collect_entries(node: &AutocompleteNode, entries: &mut Vec<AutocompleteEntry>) {
            if let Some(ref entry) = node.entry {
                entries.push(entry.clone());
            }
            for child in node.children.values() {
                collect_entries(child, entries);
            }
        }

        // Rebuild for each prefix
        let chars: Vec<char> = word.chars().collect();
        for i in 0..=chars.len() {
            let prefix: String = chars[..i].iter().collect();

            if let Some(node) = self.find_node_mut(&prefix) {
                let mut entries = Vec::new();
                collect_entries(node, &mut entries);

                // Sort by frequency (descending)
                entries.sort_by_key(|e| Reverse(e.frequency));
                entries.truncate(self.max_suggestions);

                node.top_suggestions = entries;
            }
        }
    }
}

/// Search history with autocomplete
pub struct SearchHistory {
    autocomplete: Autocomplete,
    history: Vec<String>,
    max_history: usize,
}

impl SearchHistory {
    pub fn new(max_suggestions: usize, max_history: usize) -> Self {
        Self {
            autocomplete: Autocomplete::new(max_suggestions),
            history: Vec::new(),
            max_history,
        }
    }

    /// Record a search query
    pub fn record_search(&mut self, query: &str) {
        // Add to autocomplete
        self.autocomplete.add(query);

        // Add to history
        self.history.push(query.to_string());
        if self.history.len() > self.max_history {
            self.history.remove(0);
        }
    }

    /// Get suggestions for query
    pub fn suggest(&self, prefix: &str) -> Vec<String> {
        self.autocomplete
            .suggest(prefix)
            .into_iter()
            .map(|e| e.word)
            .collect()
    }

    /// Get recent searches
    pub fn recent(&self, n: usize) -> Vec<&str> {
        self.history
            .iter()
            .rev()
            .take(n)
            .map(|s| s.as_str())
            .collect()
    }
}

fn main() {
    let mut ac = Autocomplete::new(5);

    // Build vocabulary with frequencies
    let words = [
        ("hello", 100),
        ("help", 80),
        ("helicopter", 30),
        ("hero", 50),
        ("heroine", 20),
        ("world", 90),
        ("work", 85),
        ("worker", 40),
    ];

    for (word, freq) in &words {
        ac.add_with_frequency(word, *freq);
    }

    // Test suggestions
    println!("Suggestions for 'he':");
    for entry in ac.suggest("he") {
        println!("  {} (frequency: {})", entry.word, entry.frequency);
    }

    println!("\nSuggestions for 'wor':");
    for entry in ac.suggest("wor") {
        println!("  {} (frequency: {})", entry.word, entry.frequency);
    }

    // Record selection (boosts frequency)
    ac.record_selection("hero");
    ac.record_selection("hero");

    println!("\nAfter selecting 'hero' twice:");
    for entry in ac.suggest("he") {
        println!("  {} (frequency: {})", entry.word, entry.frequency);
    }

    // Search history demo
    println!("\n=== Search History Demo ===\n");

    let mut search = SearchHistory::new(5, 10);

    search.record_search("rust programming");
    search.record_search("rust tutorial");
    search.record_search("rust async");
    search.record_search("rust web framework");
    search.record_search("rust macros");

    println!("Recent searches: {:?}", search.recent(3));
    println!("Suggestions for 'rust': {:?}", search.suggest("rust"));
}

A trie for IP address routing with CIDR support.

use std::net::Ipv4Addr;

/// Route entry
#[derive(Debug, Clone)]
pub struct Route {
    pub network: Ipv4Addr,
    pub prefix_len: u8,
    pub next_hop: Ipv4Addr,
    pub interface: String,
    pub metric: u32,
}

impl Route {
    pub fn new(
        network: Ipv4Addr,
        prefix_len: u8,
        next_hop: Ipv4Addr,
        interface: &str,
        metric: u32,
    ) -> Self {
        Self {
            network,
            prefix_len,
            next_hop,
            interface: interface.to_string(),
            metric,
        }
    }

    /// Get CIDR notation
    pub fn cidr(&self) -> String {
        format!("{}/{}", self.network, self.prefix_len)
    }
}

/// Binary trie node for IP routing
#[derive(Debug, Default)]
struct IpTrieNode {
    children: [Option<Box<IpTrieNode>>; 2],
    route: Option<Route>,
}

/// IP routing table using longest prefix match
pub struct RoutingTable {
    root: IpTrieNode,
    route_count: usize,
}

impl RoutingTable {
    pub fn new() -> Self {
        Self {
            root: IpTrieNode::default(),
            route_count: 0,
        }
    }

    /// Add a route to the table
    pub fn add_route(&mut self, route: Route) {
        let bits = Self::ip_to_bits(route.network);
        let mut node = &mut self.root;

        // Traverse/create path for prefix_len bits
        for i in 0..route.prefix_len as usize {
            let bit = bits[i] as usize;
            if node.children[bit].is_none() {
                node.children[bit] = Some(Box::default());
            }
            node = node.children[bit].as_mut().unwrap();
        }

        if node.route.is_none() {
            self.route_count += 1;
        }
        node.route = Some(route);
    }

    /// Remove a route
    pub fn remove_route(&mut self, network: Ipv4Addr, prefix_len: u8) -> Option<Route> {
        let bits = Self::ip_to_bits(network);
        let mut node = &mut self.root;

        for i in 0..prefix_len as usize {
            let bit = bits[i] as usize;
            node = node.children[bit].as_mut()?;
        }

        let route = node.route.take();
        if route.is_some() {
            self.route_count -= 1;
        }
        route
    }

    /// Lookup route using longest prefix match
    pub fn lookup(&self, ip: Ipv4Addr) -> Option<&Route> {
        let bits = Self::ip_to_bits(ip);
        let mut node = &self.root;
        let mut best_match: Option<&Route> = node.route.as_ref();

        for bit in bits.iter().take(32) {
            let idx = *bit as usize;
            match &node.children[idx] {
                Some(child) => {
                    node = child;
                    if node.route.is_some() {
                        best_match = node.route.as_ref();
                    }
                }
                None => break,
            }
        }

        best_match
    }

    /// Get all routes
    pub fn routes(&self) -> Vec<&Route> {
        let mut routes = Vec::new();
        self.collect_routes(&self.root, &mut routes);
        routes
    }

    /// Get number of routes
    pub fn len(&self) -> usize {
        self.route_count
    }

    pub fn is_empty(&self) -> bool {
        self.route_count == 0
    }

    /// Check if a more specific route exists
    pub fn has_more_specific(&self, network: Ipv4Addr, prefix_len: u8) -> bool {
        let bits = Self::ip_to_bits(network);
        let mut node = &self.root;

        // Navigate to the prefix
        for i in 0..prefix_len as usize {
            let bit = bits[i] as usize;
            match &node.children[bit] {
                Some(child) => node = child,
                None => return false,
            }
        }

        // Check if there are any routes below this prefix
        self.has_routes_below(node)
    }

    // Helper: Convert IP to bit array
    fn ip_to_bits(ip: Ipv4Addr) -> [u8; 32] {
        let octets = ip.octets();
        let mut bits = [0u8; 32];

        for (i, &octet) in octets.iter().enumerate() {
            for j in 0..8 {
                bits[i * 8 + j] = (octet >> (7 - j)) & 1;
            }
        }

        bits
    }

    // Helper: Collect all routes
    fn collect_routes<'a>(&'a self, node: &'a IpTrieNode, routes: &mut Vec<&'a Route>) {
        if let Some(ref route) = node.route {
            routes.push(route);
        }

        for child in node.children.iter().flatten() {
            self.collect_routes(child, routes);
        }
    }

    // Helper: Check if node has routes below
    fn has_routes_below(&self, node: &IpTrieNode) -> bool {
        for child in node.children.iter().flatten() {
            if child.route.is_some() || self.has_routes_below(child) {
                return true;
            }
        }
        false
    }
}

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

fn main() {
    let mut rt = RoutingTable::new();

    // Add routes
    rt.add_route(Route::new(
        "0.0.0.0".parse().unwrap(),
        0,
        "192.168.1.1".parse().unwrap(),
        "eth0",
        100,
    )); // Default route

    rt.add_route(Route::new(
        "10.0.0.0".parse().unwrap(),
        8,
        "10.0.0.1".parse().unwrap(),
        "eth1",
        10,
    )); // 10.0.0.0/8

    rt.add_route(Route::new(
        "10.1.0.0".parse().unwrap(),
        16,
        "10.1.0.1".parse().unwrap(),
        "eth2",
        5,
    )); // 10.1.0.0/16

    rt.add_route(Route::new(
        "10.1.1.0".parse().unwrap(),
        24,
        "10.1.1.1".parse().unwrap(),
        "eth3",
        1,
    )); // 10.1.1.0/24

    rt.add_route(Route::new(
        "192.168.0.0".parse().unwrap(),
        16,
        "192.168.0.1".parse().unwrap(),
        "eth4",
        10,
    )); // 192.168.0.0/16

    println!("Routing table ({} routes):", rt.len());
    for route in rt.routes() {
        println!(
            "  {} -> {} via {} (metric {})",
            route.cidr(),
            route.next_hop,
            route.interface,
            route.metric
        );
    }

    // Lookup tests
    let test_ips = [
        "10.1.1.50",
        "10.1.2.100",
        "10.2.0.1",
        "192.168.1.1",
        "8.8.8.8",
    ];

    println!("\nRoute lookups:");
    for ip_str in &test_ips {
        let ip: Ipv4Addr = ip_str.parse().unwrap();
        if let Some(route) = rt.lookup(ip) {
            println!(
                "  {} -> {} (matched {})",
                ip,
                route.next_hop,
                route.cidr()
            );
        } else {
            println!("  {} -> no route", ip);
        }
    }

    // Check for more specific routes
    println!("\nMore specific routes:");
    println!(
        "  10.0.0.0/8 has more specific: {}",
        rt.has_more_specific("10.0.0.0".parse().unwrap(), 8)
    );
    println!(
        "  10.1.1.0/24 has more specific: {}",
        rt.has_more_specific("10.1.1.0".parse().unwrap(), 24)
    );
}

| Variant | Space | Lookup | Insert | Use Case |

|---------|-------|--------|--------|----------|

| Standard | O(ALPHABET * n) | O(k) | O(k) | General purpose |

| Compressed (Radix) | O(n) | O(k) | O(k) | Memory-constrained |

| PATRICIA | O(n) | O(k) | O(k) | IP routing |

| Ternary Search | O(n) | O(k + log n) | O(k + log n) | Balanced memory/speed |

| HAT-trie | O(n) | O(k) | O(k) | Cache-efficient |

1. Choose the right variant - Standard for short keys, radix for long
2. Cache suggestions - Pre-compute top-k at each node
3. Use array children for ASCII - Faster than HashMap for limited alphabet
4. Consider memory - Tries can be memory-hungry
5. Implement iterator - For traversal operations
6. Handle Unicode properly - Decide on char vs. grapheme

| Operation | Time | Space |

|-----------|------|-------|

| Insert | O(k) | O(k) new nodes |

| Search | O(k) | O(1) |

| Delete | O(k) | O(1) (lazy) |

| Prefix search | O(k + m) | O(m) results |

| Longest prefix | O(k) | O(1) |

Where k = key length, m = number of matches

1. Implement word count for each prefix
2. Add case-insensitive search

1. Build a spell checker with edit distance suggestions
2. Implement wildcard pattern matching (a*b)

1. Create a compressed radix tree
2. Implement concurrent trie with fine-grained locking

• Trie Wikipedia
• Radix Tree
• PATRICIA Trie
• fst crate - Finite state transducers

• tantivy: Full-text search engine uses FST
• rust-analyzer: Code completion
• routers: URL routing with path parameters
• radix_trie crate: Production radix trie
• DNS servers: Domain name lookup