Word Search in Trie in DSA Typescript

Mental Model

A trie stores words by sharing common letter paths, so searching a word means following its letters step-by-step down the trie branches.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word or get lost.

root
 ↓
 [c] -> [a] -> [t*]
        ↓
       [r] -> [a] -> [t*]

* means end of a word

Dry Run Walkthrough

Input: Insert words: cat, car, rat; Search word: car

Goal: Find if the word 'car' exists in the trie

Step 1: Start at root, check for 'c'

root -> [c] -> ...

Why: We begin searching from the root for the first letter

Step 2: Move to node 'c', check for 'a'

root -> [c] -> [a] -> ...

Why: Next letter 'a' must be a child of 'c'

Step 3: Move to node 'a', check for 'r'

root -> [c] -> [a] -> [r*]

Why: Next letter 'r' must be a child of 'a'

Step 4: Node 'r' marks end of word, word found

root -> [c] -> [a] -> [r*]

Why: End marker confirms 'car' is stored

Result:

root -> [c] -> [a] -> [r*]
Word 'car' found: true

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
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false; // letter path missing
      }
      node = node.children.get(char)!; // advance to child node
    }
    return node.isEndOfWord; // check end marker
  }
}

// Driver code
const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('rat');
const wordToSearch = 'car';
console.log(`Word '${wordToSearch}' found:`, trie.search(wordToSearch));

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

advance node pointer to next letter node

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

mark current node as end of a stored word

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

stop search if next letter path missing

return node.isEndOfWord; // check end marker

confirm word ends exactly here

Output

Word 'car' found: true

Complexity Analysis

Time: O(m) because we check each of the m letters in the word once during search

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

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it avoids checking all words by branching on letters

Edge Cases

Search for empty string

Returns false since no word is empty

DSA Typescript

return node.isEndOfWord; // check end marker

Search for word not inserted

Returns false when letter path missing

DSA Typescript

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

Insert duplicate word

No error, marks end of word again

DSA Typescript

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

When to Use This Pattern

When you need fast prefix or whole word search among many words, use a trie to follow letter paths efficiently.

Common Mistakes

Mistake: Not marking the end of word node, causing search to wrongly find prefixes as words
Fix: Set isEndOfWord = true at the last node of inserted word

Mistake: Returning true if all letters found but ignoring end marker
Fix: Check isEndOfWord before confirming word exists

Summary

Stores words by branching on letters to enable fast search.

Use when you want quick word or prefix lookup among many words.

The key is following letter nodes step-by-step and checking end markers.