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.