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

Recall & Review

beginner

What is a Trie and why is it used for strings?

A Trie is a tree-like data structure that stores strings by sharing common prefixes. It is used to efficiently search, insert, and delete strings, especially when many strings share prefixes.

beginner

Why can't a hash map efficiently handle prefix-based string queries?

A hash map treats each string as a whole key and does not store information about prefixes. It cannot efficiently find all strings starting with a given prefix without checking every key.

intermediate

How does a Trie improve prefix search compared to a hash map?

A Trie stores strings character by character in a tree structure, allowing quick traversal to the node representing the prefix. This makes prefix searches fast and efficient without scanning all keys.

intermediate

What is a real-life example where Trie is better than a hash map for strings?

In autocomplete systems, Trie quickly finds all words starting with typed letters, while hash maps would need to check all stored words, making Trie faster and more suitable.

intermediate

What is a limitation of using a hash map for string storage compared to Trie?

Hash maps use more memory when storing many strings with common prefixes because they store each string separately, while Trie shares prefix nodes, saving space.

What data structure is best for fast prefix searches in strings?

A Trie

B Hash Map

C Array

D Stack

Trie stores strings by prefixes, enabling fast prefix searches.

Why can't hash maps efficiently find all strings starting with a prefix?

A They only store numbers

B They use too much memory

C They are slower than arrays

D They store strings as whole keys without prefix info

Hash maps treat keys as whole strings, so prefix info is not stored.

Which of these is a key advantage of Trie over hash map?

A Faster insertion of numbers

B Supports prefix search efficiently

C Uses less memory for unrelated strings

D Better for sorting integers

Trie is designed to efficiently support prefix-based operations.

In which scenario is Trie preferred over hash map?

A Storing unrelated keys

B Counting unique numbers

C Autocomplete feature

D Simple key-value lookup

Autocomplete requires fast prefix search, which Trie supports well.

What does a Trie node typically represent?

A A character in a string

B A whole string

C An integer value

D A hash code

Each Trie node represents one character in the stored strings.

Explain why a Trie is better than a hash map for prefix-based string searches.

Think about how strings are stored and searched.

Describe a real-world example where using a Trie is more efficient than a hash map for strings.

Consider typing suggestions on your phone.

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