Trie Search Operation in DSA Typescript

Mental Model

A trie stores words by linking letters in a tree. Searching means following letters step-by-step to find if a word exists.

Analogy: Imagine a phone book where each letter leads you to the next page. To find a name, you turn pages letter by letter until you reach the full name or find it missing.

root
 ↓
 t -> r -> i -> e -> [end]

Each arrow points to the next letter node.
[end] marks a complete word.

Dry Run Walkthrough

Input: Trie contains words: 'to', 'tea', 'ted', 'ten'. Search for 'tea'.

Goal: Check if the word 'tea' exists in the trie.

Step 1: Start at root node, look for child 't'

root -> [t]

Why: We begin search by matching first letter 't'

Step 2: Move to node 't', look for child 'e'

root -> t -> [e]

Why: Next letter 'e' must be found under 't'

Step 3: Move to node 'e', look for child 'a'

root -> t -> e -> [a]

Why: Next letter 'a' must be found under 'e'

Step 4: Move to node 'a', check if it marks end of word

root -> t -> e -> a -> [end]

Why: Confirm 'a' node marks end of 'tea' to ensure full word match

Result:

root -> t -> e -> a -> [end]
Word 'tea' 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 next 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 missing, word not found
      }
      node = node.children.get(char)!; // move to next letter node
    }
    return node.isEndOfWord; // true if full word matched
  }
}

// Driver code
const trie = new Trie();
['to', 'tea', 'ted', 'ten'].forEach(word => trie.insert(word));
const wordToSearch = 'tea';
console.log(`Word '${wordToSearch}' found:`, trie.search(wordToSearch));

node = node.children.get(char)!;

advance to next node matching current letter

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

stop search early if letter missing

return node.isEndOfWord;

confirm full word matched by checking end marker

Output

Word 'tea' found: true

Complexity Analysis

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

Space: O(1) for search since no extra space grows with input during search

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

Edge Cases

Search for empty string

Returns false because empty word is not stored

DSA Typescript

return node.isEndOfWord;

Search for word not in trie

Returns false immediately when a letter is missing

DSA Typescript

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

Search for prefix but not full word

Returns false if prefix exists but isEndOfWord is false

DSA Typescript

return node.isEndOfWord;

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use trie search because it follows letters stepwise without scanning all words.

Common Mistakes

Mistake: Not checking if the last node marks end of word, causing false positives on prefixes
Fix: Always check isEndOfWord after traversing all letters

Mistake: Returning true as soon as letters match without confirming full word
Fix: Return true only if isEndOfWord is true at last letter node

Summary

It checks if a word exists by following letter nodes step-by-step in the trie.

Use it when you want fast word lookup among many stored words.

The key is to confirm the last letter node marks the end of a complete word.