Trie | Dheerendra Varma

What is a Trie?

A trie (from retrieval) is a tree in which each path from the root to a marked node spells a complete word. Each node represents a single character, and nodes at the same depth share a common prefix. The root represents the empty prefix.

The critical property: shared prefixes are stored exactly once. Inserting "cat", "car", and "card" creates a single path for "ca", then branches at "r"/"t". Looking up any word costs O(L) where L is the word's length — independent of how many words are stored. No hash computation, no collision handling, and the traversal simultaneously discovers all words sharing a prefix.

Applications

Search engine autocomplete stores billions of queries and must instantly retrieve all completions for a typed prefix. Spell checkers use tries to find the closest valid word. IP routers use binary tries (one bit per level) for longest-prefix matching — finding which routing rule applies to an IP address. T9 predictive text maps digit sequences to word candidates. Word games like Scrabble require checking if an arbitrary substring is a valid word — a trie answers this in O(L). Genome sequence databases use specialised tries (suffix trees) for substring search.

Representations

The standard trie uses a hash map for children, supporting any character set with minimal wasted memory on sparse alphabets.

use std::collections::HashMap;
 
#[derive(Default, Debug)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
}
 
struct Trie {
    root: TrieNode,
}

After inserting "app", "apple", and "apply":

root
 └─ 'a'
     └─ 'p'
         └─ 'p' [end]
             ├─ 'l'
             │   └─ 'e' [end]
             └─ 'l'
                 └─ 'y' [end]

Wait — "app" and "apple"/"apply" share the 'l' path but branch at 'e'/'y'. The corrected structure:

root
 └─ 'a'
     └─ 'p'
         └─ 'p' [end]            ← "app"
             └─ 'l'
                 ├─ 'e' [end]    ← "apple"
                 └─ 'y' [end]    ← "apply"

The alternative fixed-array representation uses [Option<Box<TrieNode>>; 26] for lowercase English only. Array indexing makes character lookup O(1) with no hash overhead, at the cost of 26 pointers per node regardless of how many children are actually used.

Operations and Time Complexity

Operation	Time	Notes
insert	O(L)	L = length of word
search	O(L)	Exact match
starts_with	O(L)	Prefix check
delete	O(L)	Walk down, mark is_end = false
count_words_with_prefix	O(P + W)	P = prefix len, W = chars in matches
Space per word	O(L) worst case	Shared prefixes amortize cost

Implementation in Rust

use std::collections::HashMap;
 
#[derive(Default)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end: bool,
}
 
struct Trie {
    root: TrieNode,
}
 
impl Trie {
    fn new() -> Self {
        Trie { root: TrieNode::default() }
    }
 
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_default();
        }
        node.is_end = true;
    }
 
    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            match node.children.get(&ch) {
                Some(n) => node = n,
                None    => return false,
            }
        }
        node.is_end
    }
 
    fn starts_with(&self, prefix: &str) -> bool {
        let mut node = &self.root;
        for ch in prefix.chars() {
            match node.children.get(&ch) {
                Some(n) => node = n,
                None    => return false,
            }
        }
        true
    }
 
    fn count_words_with_prefix(&self, prefix: &str) -> usize {
        let mut node = &self.root;
        for ch in prefix.chars() {
            match node.children.get(&ch) {
                Some(n) => node = n,
                None    => return 0,
            }
        }
        Self::count_all(node)
    }
 
    fn count_all(node: &TrieNode) -> usize {
        let self_count = if node.is_end { 1 } else { 0 };
        self_count + node.children.values().map(Self::count_all).sum::<usize>()
    }
}
 
fn main() {
    let mut trie = Trie::new();
    for word in ["app", "apple", "apply", "application", "apt"] {
        trie.insert(word);
    }
    println!("{}", trie.search("apple"));             // true
    println!("{}", trie.search("ap"));                // false (not a complete word)
    println!("{}", trie.starts_with("ap"));           // true
    println!("{}", trie.count_words_with_prefix("app")); // 4
    println!("{}", trie.count_words_with_prefix("apt")); // 1
}

Fundamental Algorithms and Problems

Autocomplete — DFS from Prefix Node

Find all words in the trie that start with a given prefix. Walk to the prefix node, then DFS from there, collecting every node where is_end is true. The path accumulated during DFS is the word.

fn autocomplete(trie: &Trie, prefix: &str) -> Vec<String> {
    let mut node = &trie.root;
    for ch in prefix.chars() {
        match node.children.get(&ch) {
            Some(n) => node = n,
            None    => return vec![],
        }
    }
    let mut results = Vec::new();
    let mut current = prefix.to_string();
    collect_words(node, &mut current, &mut results);
    results
}
 
fn collect_words(node: &TrieNode, current: &mut String, results: &mut Vec<String>) {
    if node.is_end { results.push(current.clone()); }
    for (&ch, child) in &node.children {
        current.push(ch);
        collect_words(child, current, results);
        current.pop();
    }
}
 
fn main() {
    let mut trie = Trie::new();
    for w in ["can", "candy", "cat", "car", "card", "care", "careful"] {
        trie.insert(w);
    }
    let mut suggestions = autocomplete(&trie, "car");
    suggestions.sort();
    println!("{:?}", suggestions); // ["car", "card", "care", "careful"]
}

Longest Common Prefix

Find the longest common prefix among all words in a list. Insert all words into the trie, then walk from the root as long as there is exactly one child and the current node is not an end of any word. The path walked is the longest common prefix.

fn longest_common_prefix(words: &[&str]) -> String {
    let mut trie = Trie::new();
    for &w in words { trie.insert(w); }
 
    let mut prefix = String::new();
    let mut node = &trie.root;
    loop {
        // Stop if current node ends a word (e.g., "flow" in ["flower","flow","flight"] would stop at "flow")
        if node.is_end || node.children.len() != 1 { break; }
        let (&ch, child) = node.children.iter().next().unwrap();
        prefix.push(ch);
        node = child;
    }
    prefix
}
 
fn main() {
    println!("{}", longest_common_prefix(&["flower", "flow", "flight"])); // "fl"
    println!("{}", longest_common_prefix(&["dog", "racecar", "car"]));    // ""
    println!("{}", longest_common_prefix(&["interview", "interval", "integer"])); // "inte"
}

Replace Words with Roots

Given a dictionary of root words and a sentence, replace every word in the sentence that has a root in the dictionary with the shortest matching root. Build a trie from the dictionary roots. For each word in the sentence, walk the trie to find the shortest prefix that is a complete root word.

fn replace_words(roots: &[&str], sentence: &str) -> String {
    let mut trie = Trie::new();
    for &root in roots { trie.insert(root); }
 
    sentence.split_whitespace()
        .map(|word| find_root(&trie, word).unwrap_or(word).to_string())
        .collect::<Vec<_>>()
        .join(" ")
}
 
fn find_root<'a>(trie: &Trie, word: &'a str) -> Option<&'a str> {
    let mut node = &trie.root;
    for (i, ch) in word.char_indices() {
        match node.children.get(&ch) {
            Some(n) => {
                node = n;
                if node.is_end { return Some(&word[..=i]); } // found shortest root
            }
            None => break,
        }
    }
    None
}
 
fn main() {
    let roots = ["cat", "bat", "rat"];
    let sentence = "the cattle was rattled by the battery";
    println!("{}", replace_words(&roots, sentence));
    // "the cat was rat by the bat"
}

Maximum XOR Pair — Binary Trie

For each number treated as a 32-bit binary string, find the pair (a, b) in the array that maximises a XOR b. Insert all numbers into a binary trie (one bit per level). For each number, greedily traverse the trie preferring the opposite bit at each level — choosing the opposite bit maximises the XOR contribution of that bit position.

struct XorTrie {
    children: [Option<Box<XorTrie>>; 2],
}
 
impl XorTrie {
    fn new() -> Self { XorTrie { children: [None, None] } }
 
    fn insert(&mut self, num: i32) {
        let mut node = self;
        for bit in (0..32).rev() {
            let b = ((num >> bit) & 1) as usize;
            if node.children[b].is_none() {
                node.children[b] = Some(Box::new(XorTrie::new()));
            }
            node = node.children[b].as_mut().unwrap();
        }
    }
 
    fn max_xor_with(&self, num: i32) -> i32 {
        let mut node = self;
        let mut xor = 0i32;
        for bit in (0..32).rev() {
            let b = ((num >> bit) & 1) as usize;
            let want = 1 - b; // prefer opposite bit to maximise XOR
            if node.children[want].is_some() {
                xor |= 1 << bit;
                node = node.children[want].as_ref().unwrap();
            } else if let Some(same) = &node.children[b] {
                node = same;
            } else {
                break;
            }
        }
        xor
    }
}
 
fn find_max_xor(nums: &[i32]) -> i32 {
    let mut trie = XorTrie::new();
    for &n in nums { trie.insert(n); }
    nums.iter().map(|&n| trie.max_xor_with(n)).max().unwrap_or(0)
}
 
fn main() {
    println!("{}", find_max_xor(&[3, 10, 5, 25, 2, 8])); // 28  (5 XOR 25 = 28)
    println!("{}", find_max_xor(&[0, 0]));                // 0
}

Count Unique Words with a Given Prefix

Given a list of search queries and a prefix, count how many distinct stored words share that prefix. The trie automatically deduplicates: inserting a word twice still marks the same is_end node. The count_words_with_prefix method from the implementation section handles this directly.

fn main() {
    let mut trie = Trie::new();
    let queries = ["apple", "app", "application", "apply", "banana", "band", "bandana"];
    for &q in &queries { trie.insert(q); }
 
    println!("{}", trie.count_words_with_prefix("app"));  // 4: app, apple, application, apply
    println!("{}", trie.count_words_with_prefix("ban"));  // 3: banana, band, bandana
    println!("{}", trie.count_words_with_prefix("xyz"));  // 0
    println!("{}", trie.count_words_with_prefix(""));     // 7: all words
}