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.