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.