Trie Search Operation in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths down the tree represent words.

beginner

What does the search operation in a Trie do?

The search operation checks if a given word exists in the Trie by following nodes corresponding to each character of the word. If all characters are found and the last node marks the end of a word, the search returns true.

beginner

In Trie search, what does it mean if a character node is missing during traversal?

If a character node is missing while traversing the Trie for a word, it means the word does not exist in the Trie, so the search returns false.

intermediate

Why do we check the 'end of word' flag in the last node during Trie search?

Because some words can be prefixes of others, the 'end of word' flag confirms that the path corresponds to a complete word stored in the Trie, not just a prefix.

intermediate

What is the time complexity of searching a word in a Trie?

The time complexity is O(m), where m is the length of the word being searched, because the search visits one node per character.

What does the Trie search operation return if the word is not found?

A undefined

B true

C null

D false

If the word is not found in the Trie, the search operation returns false.

During Trie search, what happens if a character node is missing?

A Continue searching next character

B Return false immediately

C Mark word as found

D Restart search from root

If a character node is missing, the word cannot be in the Trie, so search returns false immediately.

What does the 'end of word' flag indicate in a Trie node?

A Word ends at this node

B Node is root

C Node has children

D Node is empty

The 'end of word' flag marks that a complete word ends at this node.

What is the main advantage of using a Trie for search?

A Faster than hash tables for all operations

B Automatically sorts words

C Search time depends on word length, not number of words

D Uses less memory than arrays

Trie search time depends on the length of the word, not the total number of words stored.

If the word 'cat' is stored in a Trie, which nodes are visited during search?

A c -> a -> t

B c -> t -> a

C a -> c -> t

D t -> a -> c

The search visits nodes in the order of the word's characters: c, then a, then t.

Explain step-by-step how the Trie search operation works for the word 'dog'.

Think about checking each character one by one and the end of word flag.

Why is the 'end of word' flag important in Trie search, especially when words share prefixes?

Consider the difference between 'cat' and 'caterpillar'.

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