Prefix Search Using Trie in DSA C++ - 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 from the root to nodes represent prefixes of stored words.

beginner

How does a Trie help in prefix search?

A Trie allows quick prefix search by following the path of characters from the root node. If the prefix exists, the search reaches the node representing the last character of the prefix, enabling retrieval of all words starting with that prefix.

intermediate

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

The time complexity is O(m), where m is the length of the prefix. This is because the search follows the path character by character without scanning all stored words.

beginner

Explain the role of the 'isEndOfWord' flag in a Trie node.

The 'isEndOfWord' flag marks if a node corresponds to the last character of a valid word stored in the Trie. It helps distinguish between prefixes and complete words during search and retrieval.

beginner

What happens if a prefix is not found in a Trie during search?

If the prefix path does not exist in the Trie, the search stops early, indicating no words start with that prefix. This makes prefix search efficient by avoiding unnecessary checks.

What does each node in a Trie represent?

A A character of a string

B A whole word

C An integer value

D A prefix length

Each node in a Trie represents a single character of the stored strings.

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

A Sorts words alphabetically

B Faster search by following character paths

C Stores only numbers

D Uses less memory than arrays

Trie allows fast prefix search by following the path of characters without scanning all words.

What does the 'isEndOfWord' flag indicate in a Trie node?

A Node has no children

B Node is the root of the Trie

C Node is the last character of a stored word

D Node stores a prefix length

'isEndOfWord' marks the end of a valid word in the Trie.

If a prefix is not found in a Trie, what happens?

A Search stops early, no words with that prefix

B All words are returned

C Trie deletes the prefix

D Search continues to the end

Search stops early if prefix path does not exist, indicating no matching words.

What is the time complexity of prefix search in a Trie for prefix length m?

A O(m * n)

B O(n)

C O(log n)

D O(m)

Prefix search time depends only on prefix length m, so it is O(m).

Describe how a Trie is used to perform prefix search.

Think about how you follow letters step-by-step in a tree.

Explain why prefix search in a Trie is efficient compared to scanning all words.

Consider how you find words starting with 'app' without checking every word.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To reverse strings quickly

B. To sort words alphabetically

C. To store words in a hash table

D. To efficiently find all words that start with a given prefix

Solution

1. Step 1: Understand Trie usage

   A Trie stores characters of words in a tree structure, allowing quick prefix lookups.

2. Step 2: Identify prefix search goal

   Prefix search means finding all words starting with a given prefix efficiently, which Trie supports well.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option D

4. Quick Check:

   Trie = Prefix search efficiency [OK]

Hint: Trie is built for prefix-based fast searches [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is a hash table
• Assuming Trie reverses strings

2. Which of the following is the correct way to declare a Trie node in C++?

easy

A. struct TrieNode { bool isEnd; TrieNode* children[26]; };

B. struct TrieNode { int value; TrieNode children; };

C. class TrieNode { bool isEnd; vector<int> children; };

D. struct TrieNode { bool isEnd; TrieNode children[]; };

Solution

1. Step 1: Check Trie node structure

   A Trie node typically has a boolean to mark word end and an array of pointers for children nodes.

2. Step 2: Match correct syntax

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; correctly declares a boolean and an array of 26 pointers for English lowercase letters.

3. Final Answer:

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; -> Option A

4. Quick Check:

   Trie node = bool + pointer array [OK]

Hint: Trie nodes have boolean + fixed-size pointer array [OK]

Common Mistakes:

• Using vector<int> instead of pointers
• Missing pointer (*) in children array
• Declaring children as single object, not array

3. Given the following code snippet, what will be the output after inserting words "cat", "car", "dog" and searching prefix "ca"?

Trie trie;
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
vector<string> result = trie.searchPrefix("ca");
for (auto &word : result) std::cout << word << " ";

medium

A. cat car

B. dog

C. cat dog car

D. car cat dog

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. Trie stores them by characters.

2. Step 2: Search prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   cat car -> Option A

4. Quick Check:

   Prefix "ca" matches "cat" and "car" [OK]

Hint: Search returns words starting exactly with prefix [OK]

Common Mistakes:

• Including words without the prefix
• Assuming order is alphabetical by default
• Confusing prefix search with full word search

4. Identify the bug in this Trie insert function snippet:

void insert(string word) {
  TrieNode* node = root;
  for (char c : word) {
    int index = c - 'a';
    if (!node->children[index])
      node->children[index] = new TrieNode();
    node = node->children[index];
  }
  node->isEnd = false;
}

medium

A. Children array should be vector, not array

B. isEnd should be set to true after insertion

C. Index calculation is incorrect

D. Root node is not initialized

Solution

1. Step 1: Review isEnd assignment

   After inserting a word, the node representing last character should mark end of word by setting isEnd to true.

2. Step 2: Identify incorrect isEnd value

   Code sets isEnd to false, which is wrong and will cause search failures.

3. Final Answer:

   isEnd should be set to true after insertion -> Option B

4. Quick Check:

   Mark word end with isEnd = true [OK]

Hint: Set isEnd true at word end to mark complete word [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Forgetting to initialize root node
• Miscomputing index from character

5. You want to find all words in a Trie that start with prefix "app" and have length exactly 5. Which approach correctly applies prefix search with length filtering?

hard

A. Use a hash map instead of Trie for prefix and length search

B. Search prefix "app" and return all words regardless of length

C. Search prefix "app" in Trie, then collect words with length 5 only

D. Search all words and filter those starting with "app" and length 5

Solution

1. Step 1: Perform prefix search "app" in Trie

   Traverse Trie nodes for prefix "app" to reach subtree containing all matching words.

2. Step 2: Filter collected words by length 5

   From subtree, collect only words whose length equals 5 to meet the length condition.

3. Final Answer:

   Search prefix "app" in Trie, then collect words with length 5 only -> Option C

4. Quick Check:

   Prefix search + length filter = Search prefix "app" in Trie, then collect words with length 5 only [OK]

Hint: Filter length after prefix search for efficient results [OK]

Common Mistakes:

• Returning all prefix matches without length check
• Filtering all words instead of prefix subtree
• Using hash map losing prefix search efficiency