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

Concept Flow - Trie vs Hash Map for Prefix Matching

Start Prefix Query

↓

Choose Data Structure

↓

Traverse Trie

↓

Match Prefix?

↓

Return Matches

↓

End

Shows how prefix matching starts, then splits into two paths: using a Trie or a Hash Map, each checking for prefix matches differently.

Execution Sample

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isWord: boolean = false;
}

// Insert 'cat' and 'car' into Trie
// Check prefix 'ca'

Inserts words 'cat' and 'car' into a Trie, then checks if prefix 'ca' exists.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Create root node	root	head -> root	root: {}
2	Insert 'cat'	root -> c -> a -> t (isWord=true)	head -> root -> c -> a -> t	root: {c} c: {a} a: {t} t: {}
3	Insert 'car'	root -> c -> a -> t (isWord=true), a -> r (isWord=true)	head -> root -> c -> a -> r	root: {c} c: {a} a: {t, r} t: {} r: {}
4	Check prefix 'ca'	root -> c -> a	head -> root -> c -> a	Prefix nodes: root -> c -> a
5	Prefix 'ca' found, collect words	root -> c -> a -> t, r	head -> root -> c -> a -> t/r	Words: 'cat', 'car'
6	Hash Map keys: ['cat', 'car', 'dog']	N/A	N/A	Hash Map: {'cat': true, 'car': true, 'dog': true}
7	Check prefix 'ca' in Hash Map keys	N/A	N/A	Matches: 'cat', 'car'
8	End	N/A	N/A	Prefix matching complete

💡 All prefix matches found or no more keys to check.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Trie Nodes	{}	{root -> c -> a -> t}	{root -> c -> a -> t, r}	{root -> c -> a}	{root -> c -> a -> t, r}	N/A	N/A	N/A
Hash Map	{}	{}	{}	{}	{}	{'cat': true, 'car': true, 'dog': true}	{'cat': true, 'car': true, 'dog': true}	{'cat': true, 'car': true, 'dog': true}
Prefix Matches	[]	[]	[]	[]	['cat', 'car']	[]	['cat', 'car']	['cat', 'car']

Key Moments - 3 Insights

Why does Trie traversal stop at node 'a' when checking prefix 'ca'?

Because the prefix 'ca' corresponds to nodes root -> c -> a in the Trie, as shown in execution_table step 4. We stop traversal after matching all prefix characters.

How does Hash Map find prefix matches without a tree structure?

Hash Map checks all keys to see which start with the prefix, as in execution_table step 7. It does not traverse nodes but scans keys.

Why is Trie more efficient for prefix matching than Hash Map?

Trie directly follows prefix nodes without scanning all keys, shown in steps 4 and 5, while Hash Map scans all keys (step 7), which is slower for large data.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which nodes were added to the Trie?

A Nodes for 'c', 'a', 'r'

B Nodes for 'r' only

C Nodes for 'c', 'a', 't'

D No new nodes added

💡 Hint

Check the 'Nodes in Trie' and 'Visual State' columns at step 3.

At which step does the Trie confirm the prefix 'ca' exists?

A Step 4

B Step 6

C Step 2

D Step 7

💡 Hint

Look for the step where prefix nodes root -> c -> a are identified.

If the Hash Map had 1000 keys, how would prefix matching change compared to Trie?

A Hash Map would be faster because it uses keys directly

B Trie would be slower because it traverses nodes

C Hash Map would be slower because it scans all keys

D Both would have same speed

💡 Hint

Refer to key_moments about efficiency differences.

Concept Snapshot

Trie vs Hash Map for Prefix Matching:
- Trie stores words as paths of characters (nodes).
- Prefix matching in Trie follows nodes for each prefix char.
- Hash Map stores full words as keys; prefix match scans keys.
- Trie is efficient for large datasets with many prefixes.
- Hash Map is simpler but slower for prefix queries.
- Use Trie when prefix search speed matters.

Full Transcript

This visual execution compares Trie and Hash Map for prefix matching. We start by inserting words 'cat' and 'car' into a Trie, creating nodes for each character. The Trie traversal for prefix 'ca' follows nodes root -> c -> a, confirming the prefix exists and collecting matching words. In contrast, the Hash Map stores full words as keys and checks all keys to find those starting with 'ca'. The Trie approach is more efficient for prefix matching because it directly follows prefix nodes without scanning all keys. The Hash Map approach is simpler but slower for large datasets. Key moments include understanding why Trie traversal stops at the last prefix character node and how Hash Map scans keys for prefix matches. The visual quiz tests understanding of Trie node additions, prefix confirmation steps, and efficiency differences between Trie and Hash Map.