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.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing a large set of strings?

easy

A. Because Trie is faster for all types of lookups compared to Hash Map

B. Because Trie uses less memory than Hash Map for all data types

C. Because Hash Map cannot store strings as keys

D. Because Trie supports efficient prefix search which Hash Map cannot do easily

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form allowing prefix-based queries efficiently. Hash Map stores keys but does not support prefix queries efficiently.

2. Step 2: Compare prefix search ability

   Trie can quickly find all strings with a given prefix, while Hash Map requires checking each key individually.

3. Final Answer:

   Because Trie supports efficient prefix search which Hash Map cannot do easily -> Option D

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map cannot store strings as keys
• Assuming Trie always uses less memory
• Believing Trie is faster for all lookups

2. Which of the following is the correct way to declare a Trie node in C++ for lowercase English letters?

easy

A. struct TrieNode { TrieNode* children[26]; bool isEnd; };

B. struct TrieNode { map children; bool isEnd; };

C. struct TrieNode { vector children(26); bool isEnd; };

D. struct TrieNode { TrieNode children[26]; bool isEnd; };

Solution

1. Step 1: Understand Trie node structure for fixed alphabet

   For lowercase English letters, an array of 26 pointers is common to represent children nodes.

2. Step 2: Check syntax correctness

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; correctly declares an array of 26 TrieNode pointers and a boolean flag.

3. Final Answer:

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; -> Option A

4. Quick Check:

   Array of pointers + bool flag = struct TrieNode { TrieNode* children[26]; bool isEnd; }; [OK]

Hint: Use array of pointers for fixed alphabets in Trie nodes [OK]

Common Mistakes:

• Using vector with parentheses instead of braces
• Declaring children as objects instead of pointers
• Using map when array is simpler for fixed alphabets

3. Consider the following C++ code snippet using a Trie to insert and search strings. What will be the output?

struct TrieNode {
  TrieNode* children[26] = {nullptr};
  bool isEnd = false;
};

class Trie {
  TrieNode* root;
public:
  Trie() { root = new TrieNode(); }
  void insert(string word) {
    TrieNode* node = root;
    for (char c : word) {
      int idx = c - 'a';
      if (!node->children[idx])
        node->children[idx] = new TrieNode();
      node = node->children[idx];
    }
    node->isEnd = true;
  }
  bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
      int idx = c - 'a';
      if (!node->children[idx]) return false;
      node = node->children[idx];
    }
    return node->isEnd;
  }
};

int main() {
  Trie trie;
  trie.insert("apple");
  cout << trie.search("app") << " ";
  cout << trie.search("apple") << " ";
  trie.insert("app");
  cout << trie.search("app") << endl;
  return 0;
}

medium

A. 1 0 0

B. 0 1 1

C. 0 0 1

D. 1 1 1

Solution

1. Step 1: Trace insertions and searches

   After inserting "apple", searching "app" returns false because "app" is not marked as end. Searching "apple" returns true. After inserting "app", searching "app" returns true.

2. Step 2: Match outputs with options

   Outputs are: 0 (false), 1 (true), 1 (true) matching 0 1 1.

3. Final Answer:

   0 1 1 -> Option B

4. Quick Check:

   Search "app" before insert = 0, after insert = 1 [OK]

Hint: Check isEnd flag for exact word match in Trie search [OK]

Common Mistakes:

• Assuming prefix search returns true without isEnd
• Confusing insert order effects
• Ignoring isEnd flag in search

4. The following Trie insertion code has a bug. What is the error?

void insert(string word) {
  TrieNode* node = root;
  for (int i = 0; i <= word.size(); i++) {
    int idx = word[i] - 'a';
    if (!node->children[idx])
      node->children[idx] = new TrieNode();
    node = node->children[idx];
  }
  node->isEnd = true;
}

medium

A. Loop runs one extra iteration causing out-of-bounds access

B. Children array is not initialized to nullptr

C. isEnd flag is set before last character insertion

D. Index calculation should be 'a' - word[i] instead of word[i] - 'a'

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.size(), which means it accesses word[word.size()] causing out-of-bounds error.

2. Step 2: Identify correct loop condition

   The loop should run i < word.size() to avoid invalid access.

3. Final Answer:

   Loop runs one extra iteration causing out-of-bounds access -> Option A

4. Quick Check:

   Loop boundary off by one = Loop runs one extra iteration causing out-of-bounds access [OK]

Hint: Use i < size(), not i <= size() for string indexing [OK]

Common Mistakes:

• Ignoring off-by-one errors in loops
• Confusing index calculation signs
• Assuming children array auto-initializes

5. You want to find all words in a dictionary that start with a given prefix efficiently. Why is a Trie better than a Hash Map for this task, and how would you implement the prefix search?

hard

A. Trie stores words in sorted order; implement prefix search by binary search on keys

B. Hash Map stores keys with prefix hashing; implement prefix search by hashing prefix and returning all keys

C. Trie stores words in a tree allowing prefix traversal; implement prefix search by traversing nodes for prefix then DFS for all descendants

D. Hash Map supports prefix search natively; implement prefix search by direct lookup

Solution

1. Step 1: Understand Trie prefix storage

   Trie nodes represent characters; prefix corresponds to a path in the Trie. This allows direct traversal to prefix node.

2. Step 2: Implement prefix search

   Traverse Trie nodes for prefix characters, then perform DFS from that node to collect all words starting with prefix.

3. Step 3: Compare with Hash Map

   Hash Map keys are unordered; no direct way to find all keys with a prefix without checking all keys.

4. Final Answer:

   Trie stores words in a tree allowing prefix traversal; implement prefix search by traversing nodes for prefix then DFS for all descendants -> Option C

5. Quick Check:

   Prefix traversal + DFS = Trie advantage [OK]

Hint: Use Trie traversal + DFS for prefix search, Hash Map can't do this fast [OK]

Common Mistakes:

• Assuming Hash Map supports prefix search directly
• Confusing Trie with sorted array binary search
• Ignoring need to explore descendants after prefix