Why Trie Exists and What Hash Map Cannot Do for Strings in DSA C++ - Why This Pattern

Mental Model

A trie stores strings by sharing common beginnings, making prefix searches fast and memory efficient. Hash maps can't do this because they treat each string as a separate key without sharing parts.

Analogy: Imagine a tree of roads where each road letter leads to the next letter in words. If many words start the same way, they share the same roads. A hash map is like separate houses with no shared roads, so it can't quickly find all words starting with the same letters.

root
 ↓
 a -> p -> p -> l -> e -> [end]
       ↓
       e -> [end]

Each arrow is a letter link, sharing common paths for words like "apple" and "ape".

Dry Run Walkthrough

Input: Insert words: "apple", "ape", "bat"; then search for prefix "ap"

Goal: Show how trie shares prefix paths for fast prefix search, unlike hash map

Step 1: Insert 'apple' letter by letter creating new nodes

root -> a -> p -> p -> l -> e -> [end]

Why: We build the path for 'apple' from root, each letter a new node

Step 2: Insert 'ape' sharing 'a' and 'p' nodes, then add 'e'

root -> a -> p -> p -> l -> e -> [end]
           ↓
           e -> [end]

Why: 'ape' shares 'a' and 'p' nodes with 'apple', saving space

Step 3: Insert 'bat' creating new branch from root

root -> a -> p -> p -> l -> e -> [end]
           ↓
           e -> [end]
  ↓
  b -> a -> t -> [end]

Why: 'bat' starts differently, so new branch from root is needed

Step 4: Search prefix 'ap' by following nodes 'a' then 'p'

root -> [a] -> [p] -> p -> l -> e -> [end]
           ↓
           e -> [end]
  ↓
  b -> a -> t -> [end]

Why: We can quickly find all words starting with 'ap' by following shared nodes

Result:

root -> a -> p -> p -> l -> e -> [end]
           ↓
           e -> [end]
  ↓
  b -> a -> t -> [end]
Prefix 'ap' found with words: 'apple', 'ape'

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c]; // advance curr to next node
        }
        curr->isEndOfWord = true; // mark end of word
    }

    bool startsWith(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) {
                return false; // prefix not found
            }
            curr = curr->children[c]; // advance curr to next node
        }
        return true; // prefix found
    }

    void collectAllWords(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEndOfWord) {
            results.push_back(prefix); // add complete word
        }
        for (auto& pair : node->children) {
            collectAllWords(pair.second, prefix + pair.first, results); // recurse children
        }
    }

    vector<string> getWordsWithPrefix(const string& prefix) {
        vector<string> results;
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) {
                return results; // empty if prefix not found
            }
            curr = curr->children[c];
        }
        collectAllWords(curr, prefix, results); // collect all words under prefix
        return results;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("ape");
    trie.insert("bat");

    string prefix = "ap";
    if (trie.startsWith(prefix)) {
        vector<string> words = trie.getWordsWithPrefix(prefix);
        cout << "Words with prefix '" << prefix << "':\n";
        for (const string& w : words) {
            cout << w << "\n";
        }
    } else {
        cout << "No words found with prefix '" << prefix << "'\n";
    }
    return 0;
}

curr = curr->children[c]; // advance curr to next node

advance curr to next node -- traverse or create path for each letter

curr->isEndOfWord = true; // mark end of word

mark node as end of a complete word

if (curr->children.find(c) == curr->children.end()) { return false; }

check if prefix letter exists; if not, prefix not found

collectAllWords(curr, prefix, results);

collect all words starting from prefix node recursively

Output

Words with prefix 'ap':

apple

ape

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is number of words with that prefix, because we traverse prefix nodes then collect words.

Space: O(n * l) where n is number of words and l is average length, due to storing nodes for shared prefixes.

vs Alternative: Hash maps store whole strings separately, so prefix search is O(n * l) scanning all keys, slower than trie's shared prefix traversal.

Edge Cases

Empty prefix search

Returns all words in trie since empty prefix matches all

DSA C++

if (curr->children.find(c) == curr->children.end()) { return results; }

Prefix not present

Returns empty list quickly without scanning all words

DSA C++

if (curr->children.find(c) == curr->children.end()) { return results; }

Inserting duplicate word

Marks same end node again, no duplicate nodes created

DSA C++

curr->isEndOfWord = true; // mark end of word

When to Use This Pattern

When a problem needs fast prefix searches or autocomplete, reach for trie because it shares prefix paths and avoids scanning all keys like hash maps.

Common Mistakes

Mistake: Trying to use hash map keys for prefix search by scanning all keys
Fix: Use trie to share prefix nodes and traverse only needed parts

Mistake: Not marking end of word in trie nodes
Fix: Set isEndOfWord true at last letter node to distinguish full words

Summary

Trie stores strings by sharing common prefixes for efficient prefix search.

Use trie when you need fast prefix queries or autocomplete features.

The key insight is that shared prefix paths save time and space compared to separate keys.