Prefix Search Using Trie in DSA C++ - Build from Scratch

Prefix Search Using Trie

📖 Scenario: Imagine you are building a simple search feature for a phone contacts app. When a user types the first few letters of a name, the app should quickly show all contacts starting with those letters.

🎯 Goal: Build a Trie data structure to store contact names and implement a prefix search function that returns all contacts starting with a given prefix.

📋 What You'll Learn

Create a TrieNode class with an array of children and a boolean to mark end of word

Create a Trie class with insert and prefix search methods

Insert given contact names into the Trie

Search and print all contacts starting with a given prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with a prefix.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create TrieNode and Trie classes with insert method

Create a class called TrieNode with a public array children of size 26 initialized to nullptr and a boolean isEndOfWord set to false. Then create a class called Trie with a public root node of type TrieNode* initialized in the constructor. Add a public method insert that takes a string word and inserts it into the Trie.

DSA C++

// Define TrieNode and Trie classes
// Your code here

Hint

Remember to initialize all children pointers to nullptr and set isEndOfWord to false in TrieNode constructor.

2

Insert given contacts into the Trie

Create a vector<string> called contacts with these exact names: "alice", "bob", "alex", "albert", "bobby". Then create a Trie object called trie and insert each contact from contacts into trie using the insert method.

DSA C++

#include 

// Create vector contacts with "alice", "bob", "alex", "albert", "bobby"
// Create Trie object trie
// Insert each contact into trie
// Your code here

Hint

Use a for loop to insert each contact from the vector into the Trie.

3

Add prefix search method to Trie

Add a public method TrieNode* searchPrefix(string prefix) to the Trie class. This method should return the node where the prefix ends or nullptr if prefix is not found. Use a for loop with variable c to traverse the Trie nodes for each character in prefix.

DSA C++

    TrieNode* searchPrefix(string prefix) {
        // Your code here
    }

Hint

Traverse the Trie nodes for each character in the prefix. If any character path is missing, return nullptr. Otherwise, return the last node.

4

Print all contacts starting with a given prefix

Add a helper method void printAllWords(TrieNode* node, string prefix) in Trie that recursively prints all words starting from node by appending characters to prefix. Then in main(), call searchPrefix with "al" and if the returned node is not nullptr, call printAllWords to print all contacts starting with "al".

DSA C++

    void printAllWords(TrieNode* node, string prefix) {
        // Your code here
    }

int main() {
    vector contacts = {"alice", "bob", "alex", "albert", "bobby"};
    Trie trie;
    for (string name : contacts) {
        trie.insert(name);
    }
    // Call searchPrefix with "al" and print all words
    // Your code here
    return 0;
}

Hint

Use recursion to explore all children nodes and print words when isEndOfWord is true.

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