Trie vs Hash Map for Prefix Matching in DSA Typescript - Trade-offs & Analysis

Mental Model

A trie stores words by their letters in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs extra work.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on (trie). Searching by prefix is quick because you follow the letters. A hash map is like a pile of cards with full names; to find all starting with 'Jo', you must check each card.

Trie:
root
 ├─ j
 │   ├─ o
 │   │   ├─ h
 │   │   │   └─ n (end)
 │   │   └─ e (end)
 └─ m
     └─ a
         └─ r
             └─ y (end)

Hash Map:
{
  "john": true,
  "joe": true,
  "mary": true
}

Dry Run Walkthrough

Input: words: ["john", "joe", "mary"], prefix: "jo"

Goal: Find all words starting with prefix "jo" using trie and hash map, compare steps

Step 1: Insert "john" into trie by creating nodes j -> o -> h -> n

root -> j -> o -> h -> n[end]

Why: Build trie nodes for each letter to represent the word

Step 2: Insert "joe" into trie by adding nodes under j -> o -> e

root -> j -> o -> h -> n[end]
               └─ e[end]

Why: Add new branch for different word sharing prefix

Step 3: Insert "mary" into trie by creating nodes m -> a -> r -> y

root -> j -> o -> h -> n[end]
               └─ e[end]
      └─ m -> a -> r -> y[end]

Why: Add separate branch for unrelated word

Step 4: Search prefix "jo" in trie by following j -> o nodes

At node o with children h and e

Why: Locate prefix node to find all words starting with it

Step 5: Collect words under node o: "john" and "joe"

Found words: john, joe

Why: All words under prefix node are valid matches

Step 6: Search prefix "jo" in hash map by checking each key

Keys: john, joe, mary

Why: Hash map keys are full words, no direct prefix access

Step 7: Check keys starting with "jo": john and joe match

Found words: john, joe

Why: Filter keys manually to find prefix matches

Result:

Trie final state:
root -> j -> o -> h -> n[end]
               └─ e[end]
      └─ m -> a -> r -> y[end]
Words with prefix 'jo': john, joe

Hash Map keys:
{ "john": true, "joe": true, "mary": true }
Words with prefix 'jo': john, joe

Annotated Code

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!; // advance to child node
    }
    node.isEndOfWord = true; // mark end of word
  }

  searchPrefix(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null; // prefix not found
      }
      node = node.children.get(char)!; // advance to next node
    }
    return node; // node at end of prefix
  }

  collectWords(node: TrieNode, prefix: string, results: string[]): void {
    if (node.isEndOfWord) {
      results.push(prefix); // found a word
    }
    for (const [char, child] of node.children) {
      this.collectWords(child, prefix + char, results); // explore children
    }
  }

  getWordsWithPrefix(prefix: string): string[] {
    const node = this.searchPrefix(prefix);
    const results: string[] = [];
    if (node) {
      this.collectWords(node, prefix, results); // gather all words
    }
    return results;
  }
}

// Hash Map approach
class PrefixHashMap {
  map: Map<string, boolean> = new Map();

  insert(word: string): void {
    this.map.set(word, true); // store full word
  }

  getWordsWithPrefix(prefix: string): string[] {
    const results: string[] = [];
    for (const word of this.map.keys()) {
      if (word.startsWith(prefix)) {
        results.push(word); // filter keys by prefix
      }
    }
    return results;
  }
}

// Driver code
const words = ["john", "joe", "mary"];
const prefix = "jo";

const trie = new Trie();
const hashMap = new PrefixHashMap();

for (const w of words) {
  trie.insert(w);
  hashMap.insert(w);
}

const trieResults = trie.getWordsWithPrefix(prefix);
const hashMapResults = hashMap.getWordsWithPrefix(prefix);

console.log("Trie words with prefix '" + prefix + "': " + trieResults.join(", "));
console.log("Hash Map words with prefix '" + prefix + "': " + hashMapResults.join(", "));

node = node.children.get(char)!; // advance to child node

advance node to next letter in trie to build or search word

node.isEndOfWord = true; // mark end of word

mark current node as end of a valid word

if (!node.children.has(char)) { return null; }

stop search if prefix letter missing in trie

this.collectWords(child, prefix + char, results);

recursively collect all words under prefix node

if (word.startsWith(prefix)) { results.push(word); }

filter hash map keys by prefix match

Output

Trie words with prefix 'jo': john, joe

Hash Map words with prefix 'jo': john, joe

Complexity Analysis

Time: Trie: O(m + k) where m is prefix length and k is number of matched words; Hash Map: O(n * m) where n is number of words and m is prefix length because each key is checked

Space: Trie: O(total letters in all words) for nodes; Hash Map: O(n) for storing all words as keys

vs Alternative: Trie is faster for prefix search because it directly follows prefix letters; Hash Map requires scanning all keys, slower for large datasets

Edge Cases

Empty word list

Both trie and hash map return empty results for any prefix

DSA Typescript

if (!node.children.has(char)) { return null; }

Prefix not present

Trie search returns null early; hash map returns empty after checking all keys

DSA Typescript

if (!node.children.has(char)) { return null; }

Prefix equals a full word

Trie includes that word in results; hash map includes it if key matches

DSA Typescript

if (node.isEndOfWord) { results.push(prefix); }

When to Use This Pattern

When you need to find all words starting with a prefix efficiently, consider trie for fast prefix traversal; if data is small or prefix search is rare, hash map filtering may suffice.

Common Mistakes

Mistake: Trying to find prefix matches in hash map without scanning all keys
Fix: Explicitly check each key with startsWith to filter prefix matches

Mistake: Not marking end of word in trie nodes, causing incorrect results
Fix: Set isEndOfWord = true at last node of inserted word

Summary

Trie stores words letter by letter for fast prefix search; hash map stores full words needing filtering.

Use trie when many prefix queries require fast lookup; use hash map for simple or small datasets.

The key insight is trie nodes represent prefixes directly, enabling quick traversal without scanning all words.

Practice

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

easy

A. Trie, because it stores prefixes explicitly and allows fast prefix queries

B. Hash Map, because it stores keys with constant time lookup

C. Array, because it stores elements in order

D. Linked List, because it allows sequential access

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching means finding all strings that start with a given prefix efficiently.

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

   Trie stores prefixes explicitly in its structure, allowing quick traversal to all words sharing a prefix. Hash Map only allows exact key lookups, not prefix searches.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix queries -> Option A

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Trie stores prefixes; Hash Map does not support prefix search [OK]

Common Mistakes:

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

2. Which of the following TypeScript code snippets correctly initializes a Trie node for prefix matching?

easy

A. class TrieNode { children: object = {}; isEnd: number = 0; }

B. class TrieNode { children: string[] = []; isEnd: boolean = true; }

C. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

D. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

Solution

1. Step 1: Identify correct data types for TrieNode properties

   Children should map characters (string) to TrieNode objects. isEnd should be boolean to mark word end.

2. Step 2: Check each option's correctness

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } uses Map and boolean isEnd, which is correct. Others use wrong types or incorrect isEnd values.

3. Final Answer:

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } -> Option C

4. Quick Check:

   TrieNode children = Map [OK]

Hint: Trie children map chars to nodes; isEnd is boolean [OK]

Common Mistakes:

• Using array instead of Map for children
• Setting isEnd as number instead of boolean
• Mapping children with wrong key or value types

3. What will be the output of the following TypeScript code snippet?

const map = new Map();
map.set('app', true);
map.set('apple', true);
console.log(map.has('app'));
console.log(map.has('appl'));

medium

A. false\ntrue

B. true\ntrue

C. false\nfalse

D. true\nfalse

Solution

1. Step 1: Understand Map key lookups

   Map.has(key) returns true only if exact key exists. 'app' and 'apple' are keys, 'appl' is not.

2. Step 2: Evaluate console.log outputs

   map.has('app') is true; map.has('appl') is false because 'appl' is not a key.

3. Final Answer:

   true\nfalse -> Option D

4. Quick Check:

   Exact keys only: 'app' true, 'appl' false [OK]

Hint: Map.has checks exact keys, not prefixes [OK]

Common Mistakes:

• Assuming map.has supports prefix matching
• Confusing keys 'appl' and 'apple'
• Expecting true for partial keys

4. Consider this buggy TypeScript Trie insert method:

insert(word: string) {
  let node = this.root;
  for (let char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char);
  }
  node.isEnd = true;
}

What is the main issue causing a runtime error?

medium

A. node.children.get(char) can return undefined, causing assignment to node to fail

B. The loop variable char is not declared properly

C. The isEnd property is set before the loop

D. The root node is not initialized

Solution

1. Step 1: Analyze node.children.get(char) usage

   Even after checking node.children.has(char), node.children.get(char) can theoretically return undefined if the Map is modified concurrently or due to incorrect initialization.

2. Step 2: Identify runtime error cause

   Assigning undefined to node causes subsequent property access to fail, leading to runtime error.

3. Final Answer:

   node.children.get(char) can return undefined, causing assignment to node to fail -> Option A

4. Quick Check:

   Ensure node.children.get(char) is not undefined before assignment [OK]

Hint: Check that node.children.get(char) returns a valid TrieNode before assignment [OK]

Common Mistakes:

• Thinking Map.get() returns undefined despite prior has() check
• Overlooking need for root initialization in constructor
• Assuming object-style children access instead of Map methods

5. You want to implement a prefix search feature that returns all words starting with a given prefix from a large dictionary. Which approach is best and why?

// Approach 1: Store all words in a Hash Map and check each key for prefix match
// Approach 2: Build a Trie from all words and traverse to prefix node to collect matches

hard

A. Approach 1 is better because Hash Map lookups are O(1) and prefix checks are fast

B. Approach 2 is better because Trie traversal to prefix node is efficient and collects matches quickly

C. Both approaches are equally efficient for prefix search

D. Neither approach works well; use a sorted array with binary search instead

Solution

1. Step 1: Evaluate Approach 1 (Hash Map with prefix checks)

   Hash Map allows O(1) exact lookups but requires checking every key for prefix, which is O(n) and inefficient for large data.

2. Step 2: Evaluate Approach 2 (Trie traversal)

   Trie stores prefixes explicitly; traversing to prefix node is O(k) where k is prefix length, then collecting matches is efficient.

3. Step 3: Compare efficiency and scalability

   Trie approach scales better for prefix search due to structured prefix storage and avoids scanning all keys.

4. Final Answer:

   Approach 2 is better because Trie traversal to prefix node is efficient and collects matches quickly -> Option B

5. Quick Check:

   Prefix search = Trie traversal [OK]

Hint: Trie stores prefixes; Hash Map needs full scan for prefix [OK]

Common Mistakes:

• Assuming Hash Map prefix checks are fast
• Ignoring Trie traversal efficiency
• Thinking both approaches perform the same