Trie vs Hash Map for Prefix Matching in DSA Rust - Visual Comparison

Concept Flow - Trie vs Hash Map for Prefix Matching

Start Prefix Search

↓

Use Trie?

Yes→Traverse Trie Nodes by Characters

↓

If Node Missing -> No Match

↓

Use Hash Map?

Yes→Check All Keys for Prefix

↓

Return Matched Words

↓

Return No Match

↓

End

The flow shows choosing between Trie and Hash Map for prefix search, then traversing Trie nodes or scanning Hash Map keys to find matches.

Execution Sample

DSA Rust

use std::collections::HashMap;

#[derive(Clone)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

fn prefix_match_trie(root: &TrieNode, prefix: &str) -> Vec<String> {
    let mut current = root;
    for ch in prefix.chars() {
        match current.children.get(&ch) {
            Some(child) => current = child,
            None => return vec![],
        }
    }
    // Collect all words from prefix node
    let mut results = vec![];
    collect_words(current, prefix.to_string(), &mut results);
    results
}

fn collect_words(node: &TrieNode, mut current_word: String, results: &mut Vec<String>) {
    if node.is_end_of_word {
        results.push(current_word.clone());
    }
    for (ch, child) in node.children.iter() {
        current_word.push(*ch);
        collect_words(child, current_word.clone(), results);
        current_word.pop();
    }
}

fn prefix_match_hashmap(map: &HashMap<String, String>, prefix: &str) -> Vec<String> {
    map.keys()
        .filter(|k| k.starts_with(prefix))
        .cloned()
        .collect()
}

Complete Rust implementations: Trie uses node traversal for prefix and DFS to collect descendant words. HashMap filters keys starting with the prefix.

Execution Table

Step	Operation	Data Structure	Pointer/Index	Visual State
1	Start prefix 'app' search in Trie	Trie	At root node	root -> a -> p -> p -> ... (traversing nodes)
2	Traverse 'a' child	Trie	At node 'a'	root -> a -> p -> p -> ...
3	Traverse 'p' child	Trie	At first 'p' node	root -> a -> p -> p -> ...
4	Traverse second 'p' child	Trie	At second 'p' node	root -> a -> p -> p (prefix node found)
5	Collect all words under prefix node	Trie	At second 'p' node	Found words: 'app', 'apple', 'application'
6	Start prefix 'app' search in Hash Map	Hash Map	At first key	{'apple':..., 'banana':..., 'app':..., 'apply':...}
7	Check key 'apple'	Hash Map	Key 'apple'	Matches prefix 'app', add to results
8	Check key 'banana'	Hash Map	Key 'banana'	Does not match prefix, skip
9	Check key 'app'	Hash Map	Key 'app'	Matches prefix, add to results
10	Check key 'apply'	Hash Map	Key 'apply'	Matches prefix, add to results
11	Return matched words from Hash Map	Hash Map	All keys checked	Results: 'apple', 'app', 'apply'
12	End search	Both	-	Prefix matching complete

💡 Traversal ends when prefix nodes exhausted in Trie or all keys checked in Hash Map.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 11	Final
Current Node (Trie)	root	node 'a'	node 'p' (1st)	node 'p' (2nd)	prefix node	-	-
Matched Words (Trie)	[]	[]	[]	[]	['app', 'apple', 'application']	-	-
Hash Map Keys Checked	0	1 ('apple')	2 ('banana')	3 ('app')	4 ('apply')	4	4
Matched Words (Hash Map)	[]	['apple']	['apple']	['apple', 'app']	['apple', 'app', 'apply']	['apple', 'app', 'apply']	['apple', 'app', 'apply']

Key Moments - 3 Insights

Why does Trie traversal stop after reaching the last prefix character node?

Because in the execution_table at Step 4, we reach the node representing the last character of the prefix. From there, all descendant words share the prefix, so traversal for prefix matching stops and collection begins (Step 5).

Why does Hash Map prefix matching check all keys instead of traversing nodes?

As shown in execution_table Steps 6-10, Hash Map stores keys without structure for prefixes, so it must scan every key to check if it starts with the prefix, unlike Trie which organizes keys by characters.

What is the difference in efficiency between Trie and Hash Map for prefix matching?

Trie traversal (Steps 1-5) only follows prefix characters, making it efficient for large datasets. Hash Map scanning (Steps 6-11) checks all keys, which is slower as dataset grows.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current Trie node after Step 3?

A Node 'a'

B Second 'p' node

C First 'p' node

D Root node

💡 Hint

Check the 'Pointer/Index' column for Step 3 in execution_table.

At which step does the Hash Map prefix matching add the key 'app' to results?

A Step 9

B Step 8

C Step 7

D Step 10

💡 Hint

Look at the 'Operation' and 'Visual State' columns for Hash Map key checks in execution_table.

If the prefix was 'ban', how would the Trie traversal steps change?

A No traversal, immediate no match

B Traverse nodes root -> b -> a -> n

C Traverse nodes root -> a -> p -> p

D Traverse all nodes in Trie

💡 Hint

Refer to concept_flow and variable_tracker showing traversal by prefix characters.

Concept Snapshot

Trie vs Hash Map for Prefix Matching:
- Trie stores words in a tree by characters.
- Prefix search: traverse Trie nodes for prefix, then collect words.
- Hash Map stores keys flat; prefix search scans all keys.
- Trie is efficient for large datasets and many prefixes.
- Hash Map is simpler but slower for prefix matching.

Full Transcript

This visual execution compares prefix matching using Trie and Hash Map. Trie traversal follows nodes for each prefix character, stopping at the last prefix node to collect all descendant words. Hash Map prefix matching scans all keys to find those starting with the prefix. The execution table traces each step, showing pointer positions and matched words. Variable tracker shows how current node and matched words change. Key moments clarify why Trie traversal stops at prefix end and why Hash Map scans all keys. Visual quiz tests understanding of traversal steps and matching. The snapshot summarizes key differences: Trie is structured and efficient for prefix search, Hash Map is simpler but less efficient for this task.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Linked List, because it allows easy insertion and deletion

B. Hash Map, because it provides constant time lookup for any key

C. Array, because it stores elements in contiguous memory

D. Trie, because it stores common prefixes once and allows fast prefix queries

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching needs to find all strings starting with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix queries

   Trie stores common prefixes once and allows traversal by characters, making prefix queries fast. Hash Map is good for exact key lookup but not for prefix searches.

3. Final Answer:

   Trie, because it stores common prefixes once and allows fast prefix queries -> Option D

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Prefix queries need shared paths, so Trie is best [OK]

Common Mistakes:

• Thinking Hash Map supports prefix queries efficiently
• Confusing exact lookup with prefix search
• Assuming arrays or lists are good for prefix matching

2. Which Rust code snippet correctly declares a HashMap to store strings as keys and integers as values?

easy

A. let map = HashMap::new();

B. let map: HashMap = HashMap::new();

C. let map: std::collections::HashMap = std::collections::HashMap::new();

D. let map = HashMap();

Solution

1. Step 1: Check correct HashMap declaration syntax in Rust

   Rust requires specifying types inside angle brackets and calling HashMap::new() without parameters.

2. Step 2: Validate each option

   let map: std::collections::HashMap = std::collections::HashMap::new(); correctly declares a HashMap with String keys and i32 values using full path and new().

3. Final Answer:

   let map: std::collections::HashMap = std::collections::HashMap::new(); -> Option C

4. Quick Check:

   Correct Rust HashMap syntax = let map: std::collections::HashMap = std::collections::HashMap::new(); [OK]

Hint: Use HashMap::new() with type annotations for keys and values [OK]

Common Mistakes:

• Using parentheses instead of ::new()
• Swapping key and value types
• Omitting type annotations when needed

3. Given the following Rust code using a Trie for prefix matching, what will be the output?

struct TrieNode {
    children: std::collections::HashMap,
    is_end: bool,
}

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

fn main() {
    let mut root = TrieNode::new();
    // Insert "cat"
    let mut node = &mut root;
    for c in "cat".chars() {
        node = node.children.entry(c).or_insert(TrieNode::new());
    }
    node.is_end = true;

    // Check prefix "ca"
    let mut node = &root;
    let mut found = true;
    for c in "ca".chars() {
        if let Some(next) = node.children.get(&c) {
            node = next;
        } else {
            found = false;
            break;
        }
    }
    println!("{}", found);
}

medium

A. false

B. Compilation error

C. true

D. Runtime panic

Solution

1. Step 1: Analyze TrieNode struct definition

   TrieNode { children: HashMap, ... } creates a recursive type without indirection (e.g., Box<TrieNode>). Rust cannot compute the size of TrieNode, resulting in a compilation error.

2. Step 2: Confirm error prevents execution

   Code fails to compile, so no output or runtime behavior occurs.

3. Final Answer:

   Compilation error -> Option B

4. Quick Check:

   Recursive TrieNode without Box = compile error [OK]

Hint: Rust recursive structs require Box or Rc for children [OK]

Common Mistakes:

• Assuming prefix must be a complete word
• Confusing is_end with prefix existence
• Ignoring Rust recursive type size requirements

4. The following Rust code attempts to use a HashMap for prefix matching but has a bug. What is the bug?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 1);
    map.insert("app", 2);

    let prefix = "ap";
    let mut found = false;
    for key in map.keys() {
        if key.starts_with(prefix) {
            found = true;
            break;
        }
    }
    println!("{}", found);
}

medium

A. Inefficient prefix search due to linear scan over keys

B. Using &str keys without lifetime causes compilation error

C. HashMap keys are unordered, so starts_with check is invalid

D. No bug; code works correctly for prefix matching

Solution

1. Step 1: Analyze prefix matching approach

   The code scans all keys linearly and checks if they start with the prefix, which works but is inefficient for large data.

2. Step 2: Identify the bug type

   There is no syntax or runtime error, but the approach is inefficient compared to Trie which supports fast prefix queries.

3. Final Answer:

   Inefficient prefix search due to linear scan over keys -> Option A

4. Quick Check:

   Linear scan for prefix = inefficient [OK]

Hint: HashMap needs full key; prefix search requires scanning all keys [OK]

Common Mistakes:

• Thinking code has syntax or runtime errors
• Assuming HashMap keys are ordered
• Ignoring performance implications

5. You need to implement a system in Rust that supports fast insertion and prefix search for millions of words. Which approach is best and why?

// Option A: Use a Trie with HashMap children
// Option B: Use a HashMap storing all words as keys
// Option C: Use a sorted Vec and binary search for prefix
// Option D: Use a LinkedList of words and scan linearly

hard

A. Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length

B. HashMap, because it provides O(1) exact lookup but slow prefix search

C. Sorted Vec, because binary search helps but prefix search needs extra logic

D. LinkedList, because insertion is fast but prefix search is very slow

Solution

1. Step 1: Evaluate insertion and prefix search efficiency

   Trie allows insertion and prefix search in O(k) time, where k is prefix length, by sharing common prefixes.

2. Step 2: Compare other data structures

   HashMap is fast for exact keys but slow for prefix search. Sorted Vec requires complex prefix range search. LinkedList is slow for prefix search.

3. Final Answer:

   Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length -> Option A

4. Quick Check:

   Fast prefix search = Trie [OK]

Hint: Prefix search speed depends on prefix length, Trie is best [OK]

Common Mistakes:

• Choosing HashMap for prefix search
• Ignoring complexity of prefix range search in sorted Vec
• Underestimating LinkedList search cost