Trie vs Hash Map for Prefix Matching in DSA C++ - Trade-offs & Analysis

Mental Model

A trie stores words by their letters in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs extra work.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on (trie), versus a list of names where you check each name fully (hash map).

Trie:
root
 ↓
 a -> p -> p -> l -> e
        ↓
        r
Hash Map:
{ "apple": true, "app": true, "apricot": true }

Dry Run Walkthrough

Input: words: ["app", "apple", "apricot"], prefix: "app"

Goal: Find all words starting with prefix "app" efficiently

Step 1: Insert "app" into trie by creating nodes for 'a', 'p', 'p'

root -> a -> p -> p [end]
Hash Map: { }

Why: Build trie nodes for each letter to represent the word

Step 2: Insert "apple" by extending from existing 'app' nodes with 'l' and 'e'

root -> a -> p -> p -> l -> e [end]
Hash Map: { }

Why: Reuse existing prefix nodes, add new nodes for remaining letters

Step 3: Insert "apricot" by branching from 'a' node with 'p', 'r', 'i', 'c', 'o', 't'

root -> a -> p -> p -> l -> e [end]
           ↓
           r -> i -> c -> o -> t [end]
Hash Map: { }

Why: Create new branch for different word starting with 'ap'

Step 4: Search prefix "app" in trie by following nodes 'a' -> 'p' -> 'p'

At node 'p' (second 'p')
Words below: "app", "apple"
Hash Map: { }

Why: Traverse trie nodes matching prefix letters to reach prefix node

Step 5: Collect all words below prefix node: "app", "apple"

Result: ["app", "apple"]
Hash Map: { }

Why: Gather all words that share the prefix from trie subtree

Step 6: Search prefix "app" in hash map by checking each key if it starts with "app"

Check keys: "app" (yes), "apple" (yes), "apricot" (no)
Result: ["app", "apple"]

Why: Hash map requires scanning all keys to find prefix matches

Result:

Trie final state:
root -> a -> p -> p -> l -> e [end]
           ↓
           r -> i -> c -> o -> t [end]
Prefix "app" matches: ["app", "apple"]
Hash Map final state:
{ "app": true, "apple": true, "apricot": true }
Prefix "app" matches: ["app", "apple"]

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 isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    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->isEnd = true; // mark end of word
    }

    void dfs(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEnd) results.push_back(prefix); // collect word
        for (auto& pair : node->children) {
            dfs(pair.second, prefix + pair.first, results); // explore children
        }
    }

    vector<string> startsWith(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) return {};
            curr = curr->children[c]; // advance curr to prefix node
        }
        vector<string> results;
        dfs(curr, prefix, results); // collect all words below prefix
        return results;
    }
};

vector<string> prefixMatchHashMap(const unordered_map<string, bool>& map, const string& prefix) {
    vector<string> results;
    for (const auto& pair : map) {
        if (pair.first.compare(0, prefix.size(), prefix) == 0) {
            results.push_back(pair.first); // add matching keys
        }
    }
    return results;
}

int main() {
    vector<string> words = {"app", "apple", "apricot"};
    string prefix = "app";

    Trie trie;
    for (const string& w : words) {
        trie.insert(w); // build trie
    }

    unordered_map<string, bool> map;
    for (const string& w : words) {
        map[w] = true; // build hash map
    }

    vector<string> trieResults = trie.startsWith(prefix);
    cout << "Trie prefix matches: ";
    for (const string& w : trieResults) cout << w << " ";
    cout << endl;

    vector<string> mapResults = prefixMatchHashMap(map, prefix);
    cout << "Hash Map prefix matches: ";
    for (const string& w : mapResults) cout << w << " ";
    cout << endl;

    return 0;
}

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

advance curr to next node to build or traverse trie

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

mark current node as end of a valid word

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

stop search if prefix letter not found

dfs(curr, prefix, results); // collect all words below prefix

collect all words starting with prefix from trie subtree

if (pair.first.compare(0, prefix.size(), prefix) == 0) {

check if hash map key starts with prefix

Output

Trie prefix matches: app apple 

Hash Map prefix matches: app apple 

Complexity Analysis

Time: Trie: O(m + k) where m is prefix length and k is number of matched words; Hash Map: O(n * m) where n is number of keys and m is prefix length because each key is checked

Space: Trie: O(total letters in all words) for nodes; Hash Map: O(n) for storing all keys

vs Alternative: Trie is faster for prefix queries because it avoids scanning all keys; hash map is simpler but slower for prefix matching

Edge Cases

Empty prefix string

Trie returns all words; hash map returns all keys

DSA C++

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

Prefix not present in any word

Both return empty list

DSA C++

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

Words with shared prefixes

Trie shares nodes efficiently; hash map stores full keys separately

DSA C++

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

When to Use This Pattern

When you need to find all words starting with a prefix quickly, use a trie because it organizes words by letters, unlike a hash map which stores whole words and requires scanning all keys.

Common Mistakes

Mistake: Trying to do prefix search directly on hash map keys without scanning all keys
Fix: Implement a loop to check each key's prefix or use a trie for efficient prefix queries

Mistake: Not marking end of word in trie nodes, causing incorrect prefix matches
Fix: Set isEnd = true at the last node of each inserted word

Summary

Compares trie and hash map for finding words by prefix.

Use trie for fast prefix search; hash map for exact word lookup.

Trie stores words letter by letter, enabling quick prefix traversal.