Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Rust - Why It Works

Concept Flow - Why Trie Exists and What Hash Map Cannot Do for Strings

Start with empty Trie

↓

Insert word char by char

↓

Create nodes for chars if missing

↓

Mark end of word

↓

Search or prefix check

↓

Traverse nodes by chars

↓

Return found or not

Trie stores strings character by character in a tree, enabling prefix search and ordered traversal, unlike hash maps.

Execution Sample

DSA Rust

insert("cat")
insert("car")
insert("dog")
search("ca")
search("car")

Insert words 'cat', 'car', 'dog' into Trie, then search for prefix 'ca' and full word 'car'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t	Created nodes for 'c', 'a', 't'; mark 't' as end	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t, r	Reused 'c' and 'a'; created 'r'; mark 'r' as end	root └─ c └─ a ├─ t* └─ r*
3	Insert 'dog'	root -> c -> a -> t, r; d -> o -> g	Created nodes 'd', 'o', 'g'; mark 'g' as end	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
4	Search 'ca'	No change	Traverse 'c' then 'a'	Found prefix path: c -> a
5	Search 'car'	No change	Traverse 'c' -> 'a' -> 'r'; check end mark	Found full word 'car'

💡 Search ends when all characters matched or path missing

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
Trie Nodes	empty	root->c->a->t*	root->c->a->t*,r*	root->c->a->t*,r*; d->o->g*	same	same
Current Pointer	root	at 't' end	at 'r' end	at 'g' end	at 'a' (prefix)	at 'r' (word end)
Words Stored	0	1 ('cat')	2 ('cat', 'car')	3 ('cat', 'car', 'dog')	3	3

Key Moments - 3 Insights

Why can't a hash map efficiently find all words with a given prefix?

Hash maps store whole strings as keys without order, so they can't quickly find all keys starting with a prefix. Trie nodes represent prefixes explicitly, enabling fast prefix search as shown in steps 4 and 5.

Why does Trie store characters in nodes instead of whole words?

Storing characters allows sharing common prefixes among words, saving space and enabling prefix operations. The execution table shows nodes reused for 'c' and 'a' in 'cat' and 'car' insertions.

How does Trie mark the end of a word?

Trie marks the last character node of a word with a special flag (like '*'). This is visible in the visual state after insertions, distinguishing 'car' from prefix 'ca'.

Visual Quiz - 3 Questions

Look at the execution table, after which step does the Trie first contain two words sharing a prefix?

A After Step 1

B After Step 2

C After Step 3

D After Step 4

💡 Hint

Check the 'Nodes in Trie' and 'Visual State' columns for shared nodes after each insertion.

At which step does the Trie create nodes for a completely new prefix starting with 'd'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Pointer Changes' and 'Visual State' columns to see when 'd' branch is added.

If we search for 'ca' (a prefix), what does the Trie traversal confirm according to the execution table?

A The prefix path exists but no word ends here

B The prefix path does not exist

C A full word ends at 'a'

D The search fails immediately

💡 Hint

Refer to Step 4 in the execution table under 'Visual State' and 'Pointer Changes'.

Concept Snapshot

Trie stores strings as paths of characters in a tree.
Each node represents one character.
Common prefixes share nodes, saving space.
Trie supports fast prefix search, unlike hash maps.
Words end marked by special flags on nodes.
Useful for autocomplete, prefix matching.

Full Transcript

A Trie is a tree structure that stores strings character by character. When inserting words like 'cat' and 'car', nodes for shared prefixes 'c' and 'a' are reused, saving space. Each word's end is marked to distinguish full words from prefixes. Hash maps store whole strings as keys without order, so they cannot efficiently find all words sharing a prefix. Trie traversal follows characters step-by-step, enabling fast prefix search and ordered retrieval. This is shown by inserting words and searching prefixes in the execution table. The Trie grows by creating nodes for new characters and reusing existing nodes for shared prefixes. Searching confirms if a prefix or full word exists by traversing nodes and checking end markers.

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