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.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie data structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words, but search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Search = Check existence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct TypeScript method signature for a Trie search function that returns a boolean?

easy

A. search(word: boolean): boolean

B. search(word: number): string

C. search(word: string): void

D. search(word: string): boolean

Solution

1. Step 1: Identify input and output types for search

   The search method takes a word as a string and returns true or false, so input is string and output is boolean.

2. Step 2: Match method signature with correct types

   Only search(word: string): boolean matches the expected input and output types.

3. Final Answer:

   search(word: string): boolean -> Option D

4. Quick Check:

   Input string, output boolean [OK]

Hint: Search takes string, returns true/false [OK]

Common Mistakes:

• Using wrong input type like number or boolean
• Returning void instead of boolean
• Confusing return type with string

3. Given the following TypeScript Trie search code, what will be the output?

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');
console.log(trie.search('car'));
console.log(trie.search('cap'));

medium

A. true\ntrue

B. true\nfalse

C. false\ntrue

D. false\nfalse

Solution

1. Step 1: Check inserted words in Trie

   The words 'cat', 'car', and 'dog' are inserted into the Trie.

2. Step 2: Search for 'car' and 'cap'

   'car' exists in the Trie, so search returns true. 'cap' was not inserted, so search returns false.

3. Final Answer:

   true\nfalse -> Option B

4. Quick Check:

   Inserted words found, missing words not found [OK]

Hint: Inserted words return true, others false [OK]

Common Mistakes:

• Assuming 'cap' is found because it starts like 'car'
• Mixing true/false order in output
• Forgetting to insert words before search

4. Identify the bug in this TypeScript Trie search method:

search(word: string): boolean {
  let node = this.root;
  for (let i = 0; i <= word.length; i++) {
    const char = word[i];
    if (!node.children.has(char)) return false;
    node = node.children.get(char)!;
  }
  return node.isEndOfWord;
}

medium

A. Loop condition should be i < word.length, not <=

B. Missing check for empty string input

C. Should return true before loop ends

D. Incorrect use of non-null assertion operator (!)

Solution

1. Step 1: Analyze loop boundary in search method

   The loop runs from i = 0 to i <= word.length, which means it accesses word[word.length], an undefined index.

2. Step 2: Correct loop condition to avoid out-of-bounds

   The loop should run while i < word.length to access valid characters only.

3. Final Answer:

   Loop condition should be i < word.length, not <= -> Option A

4. Quick Check:

   Loop boundary off by one [OK]

Hint: Loop over characters with i < length, not <= length [OK]

Common Mistakes:

• Using <= causes undefined access
• Ignoring empty string edge case
• Misusing non-null assertion without checks

5. You want to modify a Trie search method to support prefix search (check if any word starts with given prefix). Which change is correct?

hard

A. Return true only if prefix is a complete word (isEndOfWord true)

B. Return false if prefix length is less than 3 characters

C. Return true as soon as all prefix characters are found, without checking isEndOfWord

D. Return true only if prefix matches exactly one word

Solution

1. Step 1: Understand prefix search goal

   Prefix search should confirm if any word starts with the given prefix, not necessarily a complete word.

2. Step 2: Adjust search logic for prefix

   Return true once all prefix characters are found in sequence, without requiring isEndOfWord to be true.

3. Final Answer:

   Return true as soon as all prefix characters are found, without checking isEndOfWord -> Option C

4. Quick Check:

   Prefix found means true, no full word check needed [OK]

Hint: Prefix search stops after matching prefix, ignores full word flag [OK]

Common Mistakes:

• Checking isEndOfWord for prefix search
• Rejecting short prefixes arbitrarily
• Requiring prefix to match exactly one word