Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Typescript - Why This Pattern

Mental Model

A trie stores words by sharing common beginnings, making it fast to find all words starting with a prefix. Hash maps can't do this efficiently because they treat each word separately.

Analogy: Imagine a tree of roads where each letter is a turn. If many words start the same way, they share the same path. A hash map is like separate houses with no shared roads, so finding all neighbors with the same street start is slow.

root
 ↓
 a -> p -> p -> l -> e
       ↓
       r -> t

Each arrow is a letter link, sharing common paths for words like 'apple' and 'apart'.

Dry Run Walkthrough

Input: words: ['apple', 'app', 'apart'], find all words starting with 'ap'

Goal: Show how trie shares prefix 'ap' to find all words starting with it quickly, unlike hash map

Step 1: Insert 'apple' letter by letter into trie

root -> a -> p -> p -> l -> e (end of 'apple')

Why: Build path for 'apple' so each letter links to next

Step 2: Insert 'app' sharing existing 'a' and 'p' nodes

root -> a -> p -> p (end of 'app') -> l -> e (end of 'apple')

Why: Reuse prefix nodes to save space and time

Step 3: Insert 'apart' sharing existing 'a' and 'p' nodes, branching to 'a' -> 'r' -> 't'

root -> a -> p -> p (end 'app') -> l -> e (end 'apple')
           ↓
           a -> r -> t (end 'apart')

Why: Add new branch for different word starting with same prefix

Step 4: Search for prefix 'ap' by following 'a' then 'p'

At node 'p' with branches to 'p' and 'a'

Why: Find node representing prefix to list all words below

Step 5: Collect all words below 'ap' node: 'app', 'apple', 'apart'

Words found: 'app', 'apple', 'apart'

Why: Trie allows quick prefix search by traversing shared nodes

Result:

root -> a -> p -> p (end 'app') -> l -> e (end 'apple')
           ↓
           a -> r -> t (end 'apart')
Words starting with 'ap': app, apple, apart

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 next node
    }
    node.isEndOfWord = true; // mark end of word
  }

  findWordsWithPrefix(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return []; // prefix not found
      }
      node = node.children.get(char)!; // advance to prefix node
    }
    const results: string[] = [];
    this._dfs(node, prefix, results); // collect all words below prefix
    return results;
  }

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

// Driver code
const trie = new Trie();
const words = ['apple', 'app', 'apart'];
for (const w of words) {
  trie.insert(w);
}
const prefix = 'ap';
const foundWords = trie.findWordsWithPrefix(prefix);
console.log(`Words starting with '${prefix}': ${foundWords.join(', ')}`);

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

advance node pointer to next letter node to build or search path

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

mark current node as end of a valid word

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

stop search if prefix letter not found

this._dfs(node, prefix, results); // collect all words below prefix

start depth-first search to gather all words sharing prefix

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

add complete word to results when end node reached

Output

Words starting with 'ap': app, apple, apart

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is total letters in matched words because we traverse prefix then collect words

Space: O(n * l) where n is number of words and l average length, for storing all nodes in trie

vs Alternative: Hash map stores full words separately, so prefix search is O(n) scanning all keys, while trie shares prefixes for faster search

Edge Cases

Empty prefix search

Returns all words in trie because empty prefix matches everything

DSA Typescript

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

Prefix not in trie

Returns empty list immediately

DSA Typescript

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

Words with shared prefix but different lengths

All words correctly found due to isEndOfWord marking

DSA Typescript

node.isEndOfWord = true;

When to Use This Pattern

When a problem asks for fast prefix search or autocomplete on many strings, reach for the trie pattern because it shares prefixes and avoids scanning all words.

Common Mistakes

Mistake: Trying to use a hash map to find all words with a prefix by scanning keys
Fix: Use a trie to share prefix nodes and collect words efficiently

Summary

A trie stores strings by sharing common prefixes to enable fast prefix searches.

Use a trie when you need to find all words starting with a prefix quickly.

The key insight is that shared prefix nodes let you avoid checking every word individually.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Trie is faster for exact string lookups than Hash Maps

B. Because Trie uses less memory than a Hash Map for all cases

C. Because Hash Maps cannot store strings as keys

D. Because Trie efficiently supports prefix-based searches and auto-completion

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form, allowing quick prefix searches. Hash Maps store keys but do not support prefix queries efficiently.

2. Step 2: Compare use cases for prefix search

   Trie can find all strings starting with a prefix quickly, which Hash Maps cannot do without scanning all keys.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches and auto-completion -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie = prefix search; Hash Map = exact key lookup [OK]

Common Mistakes:

• Thinking Hash Maps support prefix search efficiently
• Assuming Trie always uses less memory
• Believing Hash Maps cannot store strings as keys

2. Which of the following is the correct TypeScript syntax to declare a Trie node with children as a Map of characters to nodes?

easy

A. class TrieNode { children: Map = new Map(); }

B. class TrieNode { children: Map = new Map(); }

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

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

Solution

1. Step 1: Understand Map type declaration in TypeScript

   Map keys and values must be typed as Map. Here keys are characters (string), values are TrieNode.

2. Step 2: Check each option's syntax

   class TrieNode { children: Map = new Map(); } correctly declares children as Map initialized with new Map(). Others have wrong generic order or types.

3. Final Answer:

   class TrieNode { children: Map = new Map(); } -> Option A

4. Quick Check:

   Map syntax correct [OK]

Hint: Map with correct order and initialization [OK]

Common Mistakes:

• Swapping key and value types in Map
• Not initializing Map with new Map()
• Using wrong generic types for Map

3. Given the following TypeScript Trie insertion code snippet, what will be the output after inserting words ['cat', 'car', 'dog'] and searching for prefix 'ca'?

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

class Trie {
  root = new TrieNode();

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

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return true;
  }
}

const trie = new Trie();
['cat', 'car', 'dog'].forEach(w => trie.insert(w));
console.log(trie.startsWith('ca'));

medium

A. undefined

B. true

C. false

D. Error at runtime

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted. 'ca' prefix nodes are created for 'c' and 'a'.

2. Step 2: Check startsWith for 'ca'

   Traversal finds nodes for 'c' and 'a' successfully, so returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix nodes exist, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Assuming isEnd must be true for prefix check
• Expecting false if prefix is partial

4. The following TypeScript Trie search method is intended to check if a word exists. What is the bug?

search(word: string): boolean {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch)!;
  }
  return false;
}

medium

A. It always returns false even if word exists

B. It throws an error when word is empty

C. It returns true for any prefix, not full word

D. It does not check if node is null

Solution

1. Step 1: Analyze the return statement after loop

   The method returns false after the loop without checking if the last node marks end of a word.

2. Step 2: Identify missing isEnd check

   It should return node.isEnd to confirm full word presence, not just prefix.

3. Final Answer:

   It always returns false even if word exists -> Option A

4. Quick Check:

   Missing isEnd check causes always false [OK]

Hint: Check isEnd after traversal to confirm full word [OK]

Common Mistakes:

• Returning false without checking isEnd
• Confusing prefix search with full word search
• Ignoring empty string edge case

5. You want to store a large dictionary of words and quickly find all words starting with a given prefix. Why is a Trie better than a Hash Map for this, and what is a limitation of Hash Map in this scenario?

hard

A. Trie uses less memory than Hash Map; Hash Map cannot store string keys longer than 10 characters.

B. Trie supports exact word search only; Hash Map supports prefix search but slower.

C. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys.

D. Trie is slower for insertion; Hash Map is faster for prefix search.

Solution

1. Step 1: Understand Trie prefix storage

   Trie organizes words by shared prefixes in a tree, enabling quick retrieval of all words with a prefix.

2. Step 2: Understand Hash Map limitations

   Hash Map stores keys without order, so prefix search requires checking all keys, which is inefficient.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys. -> Option C

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = fast prefix search; Hash Map = no prefix search [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Assuming Trie uses less memory always
• Confusing exact search with prefix search