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.