Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Rust - Why This Pattern

Mental Model

A trie stores strings by sharing common beginnings, making it fast to find all words starting with a prefix. Hash maps can't do this efficiently because they treat each string as a whole key.

Analogy: Imagine a tree of roads where each road letter leads to the next letter in a word. If many words start the same way, they share the same roads. A hash map is like having separate locked boxes for each word, no shared roads.

root
 ↓
 a -> p -> p -> l -> e
  ↓
  t

Each arrow is a letter link, sharing common paths for words like 'apple' and 'apt'.

Dry Run Walkthrough

Input: Insert words: 'apple', 'apt', 'bat' into trie and hash map

Goal: Show how trie shares prefixes and hash map stores full words separately, making prefix search easy only in trie

Step 1: Insert 'apple' into trie

root -> a -> p -> p -> l -> e

Why: Create nodes for each letter to build the word path

Step 2: Insert 'apt' into trie

root -> a -> p -> p -> l -> e
           ↓
           t

Why: Share 'a' and 'p' nodes, add new branch for 't'

Step 3: Insert 'bat' into trie

root -> a -> p -> p -> l -> e
           ↓
           t

root -> b -> a -> t

Why: Add new branch from root for 'bat' since prefix differs

Step 4: Store words in hash map as keys

{ 'apple': true, 'apt': true, 'bat': true }

Why: Hash map stores full words as separate keys, no shared parts

Step 5: Search prefix 'ap' in trie

Traverse root -> a -> p, find subtree with 'p', 'l', 'e', 't'

Why: Trie allows quick prefix search by following letter nodes

Step 6: Search prefix 'ap' in hash map

No direct way, must check all keys for prefix

Why: Hash map treats keys as whole strings, no prefix sharing

Result:

Trie structure:
root -> a -> p -> p -> l -> e
           ↓
           t
root -> b -> a -> t

Hash map keys:
'apple', 'apt', 'bat'

Trie allows fast prefix search; hash map does not.

Annotated Code

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));
        }
        node.is_end = true;
    }

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

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

    let words = vec!["apple", "apt", "bat"];

    for &word in &words {
        trie.insert(word);
        hashmap.insert(word, true);
    }

    println!("Trie starts_with 'ap': {}", trie.starts_with("ap"));
    println!("HashMap contains keys starting with 'ap':");
    for key in hashmap.keys() {
        if key.starts_with("ap") {
            println!("{}", key);
        }
    }
}

node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));

advance or create child node for current letter to build word path

node.is_end = true;

mark end of word at last letter node

for ch in prefix.chars() { match node.children.get(&ch) { Some(next_node) => node = next_node.as_ref(), None => return false, } }

traverse trie nodes following prefix letters to check prefix existence

for &word in &words { trie.insert(word); hashmap.insert(word, true); }

insert words into both trie and hash map for comparison

for key in hashmap.keys() { if key.starts_with("ap") { println!("{}", key); } }

simulate prefix search in hash map by checking all keys

Output

Trie starts_with 'ap': true

HashMap contains keys starting with 'ap':

apple

apt

Complexity Analysis

Time: O(m) for trie insert and prefix search where m is length of word or prefix, because we follow letters one by one; O(n * m) for hash map prefix search because we check all n keys each up to length m

Space: O(n * m) for trie storing all letters nodes but shared prefixes reduce space; O(n * m) for hash map storing all full keys separately

vs Alternative: Trie is more efficient for prefix queries because it shares common prefixes, while hash map treats each string as a separate key requiring full scans for prefix search

Edge Cases

Empty string insertion

Trie marks root as end of word; hash map stores empty string key

DSA Rust

node.is_end = true;

Prefix search for string not in trie

Trie returns false immediately when missing letter node

DSA Rust

None => return false,

Words with shared prefixes

Trie shares nodes for common prefix letters, saving space

DSA Rust

node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));

When to Use This Pattern

When a problem asks for fast prefix search or autocomplete on many strings, reach for the trie pattern because it shares prefixes and avoids scanning all keys like a hash map.

Common Mistakes

Mistake: Trying to do prefix search directly on hash map keys without scanning all keys
Fix: Use a trie to store strings for efficient prefix traversal instead of relying on hash map keys

Summary

Trie stores strings by sharing common prefixes for efficient prefix search.

Use trie when you need fast prefix queries or autocomplete on many strings.

The key insight is that tries share letter nodes for prefixes, unlike hash maps that treat strings as whole keys.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Hash Map can only store numbers, not strings

B. Because Hash Map uses less memory than Trie

C. Because Trie stores strings as keys directly without splitting

D. Because Trie can efficiently find all strings with a common prefix

Solution

1. Step 1: Understand Trie prefix search ability

   Trie stores strings character by character, allowing quick prefix-based searches.

2. Step 2: Compare with Hash Map capabilities

   Hash Map stores whole strings as keys but cannot efficiently find all keys sharing a prefix.

3. Final Answer:

   Because Trie can efficiently find all strings with a common prefix -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Confusing memory usage advantages
• Believing Trie stores whole strings as keys

2. Which of the following is the correct way to declare a Trie node struct in Rust for lowercase English letters?

easy

A. struct TrieNode { children: [Option; 26], is_end: bool }

B. struct TrieNode { children: Vec<TrieNode>, is_end: bool }

C. struct TrieNode { children: HashMap, is_end: bool }

D. struct TrieNode { children: [TrieNode; 26], is_end: bool }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive structs need Box to allocate on heap to avoid infinite size.

2. Step 2: Check array size and type

   Array of 26 Option fits lowercase letters and allows empty children.

3. Final Answer:

   struct TrieNode { children: [Option; 26], is_end: bool } -> Option A

4. Quick Check:

   Use Box and Option for recursive children [OK]

Hint: Use Box and Option for recursive children array [OK]

Common Mistakes:

• Using Vec without Box causes infinite size error
• Using HashMap instead of fixed array for fixed alphabet
• Using array of TrieNode directly without Box

3. What will be the output of the following Rust code snippet using a Trie to insert and search strings?

let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
println!("{}", trie.starts_with("ca"));
println!("{}", trie.starts_with("do"));
println!("{}", trie.starts_with("bat"));

medium

A. true
false
false

B. false
true
false

C. true
true
false

D. false
false
true

Solution

1. Step 1: Insert strings into Trie

   Strings "cat", "car", and "dog" are inserted, so prefixes "ca" and "do" exist.

2. Step 2: Check starts_with queries

   "ca" matches "cat" and "car" (true), "do" matches "dog" (true), "bat" not inserted (false).

3. Final Answer:

   true true false -> Option C

4. Quick Check:

   Prefix search matches inserted prefixes [OK]

Hint: Inserted prefixes return true on starts_with [OK]

Common Mistakes:

• Assuming starts_with returns true only for full words
• Confusing starts_with with exact search
• Mixing up true/false outputs

4. Given this Rust Trie insert function snippet, what is the bug?

fn insert(&mut self, word: &str) {
  let mut node = &mut self.root;
  for c in word.chars() {
    let index = (c as usize) - ('a' as usize);
    if node.children[index].is_none() {
      node.children[index] = Some(Box::new(TrieNode::new()));
    }
    node = &mut node.children[index].as_mut().unwrap();
  }
  node.is_end = true;
}

medium

A. The index calculation assumes only lowercase letters without validation

B. The unwrap() call can cause a panic if children[index] is None

C. The loop should iterate over bytes, not chars

D. The is_end flag is set before the loop

Solution

1. Step 1: Analyze index calculation

   Index is calculated by subtracting 'a' from character code, assuming lowercase letters only.

2. Step 2: Identify missing validation

   No check if character is lowercase a-z, so uppercase or other chars cause wrong index or panic.

3. Final Answer:

   The index calculation assumes only lowercase letters without validation -> Option A

4. Quick Check:

   Index must be validated for safe access [OK]

Hint: Check character range before index calculation [OK]

Common Mistakes:

• Ignoring character validation causes panic
• Thinking unwrap() is unsafe here (it's safe after check)
• Confusing iteration over chars vs bytes

5. You want to find all words in a dictionary that start with a given prefix efficiently. Why is a Trie better than a Hash Map for this task, and how does it achieve this?

hard

A. Trie uses less memory than Hash Map for storing strings; Hash Map stores full strings wasting space

B. Trie stores words character by character, enabling fast prefix traversal; Hash Map cannot efficiently list keys by prefix

C. Trie hashes prefixes for quick lookup; Hash Map hashes full strings only

D. Trie sorts all words internally; Hash Map stores words unsorted

Solution

1. Step 1: Understand Trie's character-by-character storage

   Trie nodes represent characters, so traversing nodes follows prefix paths quickly.

2. Step 2: Compare with Hash Map key storage

   Hash Map keys are full strings; no structure to find all keys sharing a prefix efficiently.

3. Step 3: Explain prefix search advantage

   Trie traversal to prefix node then explores subtree for all matching words efficiently.

4. Final Answer:

   Trie stores words character by character, enabling fast prefix traversal; Hash Map cannot efficiently list keys by prefix -> Option B

5. Quick Check:

   Trie = prefix traversal, Hash Map = no prefix listing [OK]

Hint: Trie traverses prefix nodes; Hash Map cannot list by prefix [OK]

Common Mistakes:

• Assuming Hash Map can list keys by prefix efficiently
• Confusing hashing with prefix traversal
• Thinking Trie sorts words internally