Prefix Search Using Trie in DSA C++

Mental Model

A trie stores words by sharing common beginnings, so searching for a prefix is fast by following the shared path.

Analogy: Imagine a tree of roads where each letter is a turn; to find all streets starting with 'Ma', you just follow the path M -> a and see all branches from there.

root
 ↓
 m -> a -> n -> null
      ↓
      p -> null
      ↓
      d -> e -> null

Dry Run Walkthrough

Input: Insert words: "man", "map", "made"; then search prefix "ma"

Goal: Find if any word starts with prefix "ma" and list all such words

Step 1: Insert 'man' letter by letter

root -> m -> a -> n -> null

Why: Build path for 'man' so trie stores it

Step 2: Insert 'map' sharing prefix 'ma'

root -> m -> a -> n -> null
               ↓
               p -> null

Why: Reuse 'm' and 'a' nodes, add 'p' for 'map'

Step 3: Insert 'made' sharing prefix 'ma'

root -> m -> a -> n -> null
               ↓
               p -> null
               ↓
               d -> e -> null

Why: Add 'd' and 'e' nodes after 'a' to store 'made'

Step 4: Search prefix 'ma' by following m -> a

At node 'a' with children n, p, d

Why: Prefix 'ma' found, now list all words below

Step 5: Collect words starting with 'ma': 'man', 'map', 'made'

Words found: man, map, made

Why: All words under 'a' node start with prefix 'ma'

Result:

Words with prefix 'ma': man, map, made

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;
    void collectAllWords(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEndOfWord) results.push_back(prefix); // add word when end reached
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                collectAllWords(node->children[i], prefix + char('a' + i), results); // explore children
            }
        }
    }
public:
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) curr->children[index] = new TrieNode(); // create node if missing
            curr = curr->children[index]; // move to next node
        }
        curr->isEndOfWord = true; // mark end of word
    }

    vector<string> searchPrefix(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!curr->children[index]) return {}; // prefix not found
            curr = curr->children[index]; // move down trie
        }
        vector<string> results;
        collectAllWords(curr, prefix, results); // collect all words under prefix
        return results;
    }
};

int main() {
    Trie trie;
    trie.insert("man");
    trie.insert("map");
    trie.insert("made");

    string prefix = "ma";
    vector<string> words = trie.searchPrefix(prefix);

    cout << "Words with prefix '" << prefix << "':";
    for (string w : words) cout << " " << w << ",";
    cout << "\b \n"; // backspace to remove last comma
    return 0;
}

if (!curr->children[index]) curr->children[index] = new TrieNode();

create new node if path letter missing

curr = curr->children[index];

advance current node pointer along word letters

curr->isEndOfWord = true;

mark node as end of a valid word

if (!curr->children[index]) return {};

stop search if prefix letter missing

collectAllWords(curr, prefix, results);

gather all words starting from prefix node

if (node->isEndOfWord) results.push_back(prefix);

add word to results when end node reached

Output

Words with prefix 'ma': man, map, made

Complexity Analysis

Time: O(m + k) where m is prefix length and k is total letters in matched words because we traverse prefix then collect words

Space: O(n * l) where n is number of words and l average length, for storing trie nodes

vs Alternative: Compared to scanning all words for prefix (O(n*l)), trie reduces prefix search to O(m) plus output size

Edge Cases

Empty trie, search any prefix

Returns empty list since no words stored

DSA C++

if (!curr->children[index]) return {};

Prefix not present in trie

Returns empty list immediately

DSA C++

if (!curr->children[index]) return {};

Prefix is a whole word and also prefix to others

Returns all words starting with prefix including the prefix word itself

DSA C++

if (node->isEndOfWord) results.push_back(prefix);

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie because it shares common prefixes and speeds up search.

Common Mistakes

Mistake: Not marking the end of word node, so prefix search returns incomplete results
Fix: Set isEndOfWord = true at the last node of inserted word

Mistake: Not checking if child node exists before moving, causing null pointer errors
Fix: Always check if curr->children[index] is not null before advancing

Summary

Stores words in a tree structure sharing prefixes for fast prefix search.

Use when you want to find all words starting with a given prefix efficiently.

The key is to follow the prefix path then collect all words below that node.

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