Why Trie Exists and What Hash Map Cannot Do for Strings in DSA C++ - See It Work

Why Trie Exists and What Hash Map Cannot Do for Strings

📖 Scenario: Imagine you are building a phone directory app that stores many names. You want to quickly find all names that start with a certain prefix, like "AL" to find "ALICE", "ALBERT", and "ALFRED".Using a hash map (dictionary) can find exact names fast, but it cannot easily find all names starting with a prefix. This is where a Trie (prefix tree) helps.

🎯 Goal: Build a simple Trie data structure to store a list of names and find all names starting with a given prefix.This will show why Trie is useful and what hash maps cannot do easily with strings.

📋 What You'll Learn

Create a list of names as strings

Create a prefix string to search

Build a Trie to insert all names

Search the Trie for all names starting with the prefix

Print the list of names found with the prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete, spell checkers, and dictionaries to quickly find words by prefix.

💼 Career

Understanding Tries helps in software roles involving text processing, search optimization, and building efficient data retrieval systems.

1

Create the list of names

Create a std::vector<std::string> called names with these exact entries: "ALICE", "ALBERT", "ALFRED", "BOB", "BOBBY"

DSA C++

# Create the vector names with the given strings
# Your code here

Hint

Use std::vector<std::string> and initialize it with the exact names inside curly braces.

2

Create the prefix string to search

Create a std::string variable called prefix and set it to "AL"

DSA C++

#include 
#include 
#include 

std::vector names = {"ALICE", "ALBERT", "ALFRED", "BOB", "BOBBY"};

// Create the prefix string
# Your code here

Hint

Use std::string prefix = "AL"; to create the prefix variable.

3

Build a simple Trie and insert all names

Define a struct TrieNode with a std::vector<TrieNode*> called children of size 26 initialized to nullptr, and a bool called isEndOfWord initialized to false. Then create a class Trie with a TrieNode* root initialized in the constructor. Add a public method void insert(const std::string &word) that inserts each character of word into the Trie. Insert all names from names into the Trie using a for loop.

DSA C++

#include 
#include 
#include 

std::vector names = {"ALICE", "ALBERT", "ALFRED", "BOB", "BOBBY"};

std::string prefix = "AL";

// Define TrieNode struct and Trie class with insert method
// Insert all names into the Trie
# Your code here

Hint

Remember to create 26 children for each letter A-Z and mark the end of word.

Insert each name by looping over its characters and creating nodes if missing.

4

Search the Trie for names starting with the prefix and print them

Add a private helper method void dfs(TrieNode* node, std::string ¤t, std::vector<std::string> &result) in Trie that does a depth-first search to collect all words starting from node. Add a public method std::vector<std::string> startsWith(const std::string &prefix) that finds the node matching the prefix and calls dfs to collect all words starting with it. In main(), call startsWith(prefix) and print each found name on its own line.

DSA C++

#include 
#include 
#include 

std::vector names = {"ALICE", "ALBERT", "ALFRED", "BOB", "BOBBY"};

std::string prefix = "AL";

struct TrieNode {
    std::vector children;
    bool isEndOfWord;
    TrieNode() : children(26, nullptr), isEndOfWord(false) {}
};

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

    void insert(const std::string &word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'A';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    // Add dfs and startsWith methods here

};

int main() {
    Trie trie;
    for (const std::string &name : names) {
        trie.insert(name);
    }

    // Call startsWith and print results
    # Your code here
}

Hint

Use a depth-first search to collect all words starting from the prefix node.

Print each found name on its own line.

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