How to Implement Trie in C++: Simple Guide with Example

To implement a trie in C++, create a TrieNode class with an array or map of child nodes and a boolean to mark word endings. Then build a Trie class with methods to insert and search words by traversing these nodes.

Syntax

A TrieNode holds links to child nodes for each character and a flag to mark if a word ends here. The Trie class manages the root node and provides insert and search methods to add and find words.

• TrieNode(): Constructor initializes children and end flag.
• insert(string word): Adds a word character by character.
• search(string word): Checks if a word exists in the trie.

cpp

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    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])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    bool search(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                return false;
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

Example

This example shows how to create a trie, insert words, and search for them. It prints true if the word is found and false otherwise.

cpp

#include <iostream>
#include <string>

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    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])
                node->children[index] = new TrieNode();
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    bool search(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index])
                return false;
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");

    std::cout << std::boolalpha;
    std::cout << "Search 'apple': " << trie.search("apple") << std::endl;
    std::cout << "Search 'app': " << trie.search("app") << std::endl;
    std::cout << "Search 'appl': " << trie.search("appl") << std::endl;
    std::cout << "Search 'banana': " << trie.search("banana") << std::endl;

    return 0;
}

Output

Search 'apple': true
Search 'app': true
Search 'appl': false
Search 'banana': false

Common Pitfalls

Common mistakes include:

• Not initializing child pointers to nullptr, causing undefined behavior.
• Forgetting to mark the end of a word, so searches fail for complete words.
• Assuming input characters are lowercase letters without validation.
• Memory leaks by not freeing allocated nodes (not shown here for simplicity).

cpp

/* Wrong: Not initializing children pointers */
class WrongTrieNode {
public:
    WrongTrieNode* children[26];
    bool isEndOfWord;

    WrongTrieNode() {
        isEndOfWord = false;
        // children not initialized, may contain garbage
    }
};

/* Right: Initialize all children to nullptr */
class RightTrieNode {
public:
    RightTrieNode* children[26];
    bool isEndOfWord;

    RightTrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};

Quick Reference

• TrieNode: Holds 26 children pointers and a boolean flag.
• insert(word): Traverse or create nodes for each character, mark end.
• search(word): Traverse nodes, return true if end flag is set.
• Input words must be lowercase letters a-z for this implementation.

Key Takeaways

Initialize all child pointers to nullptr to avoid errors.

Mark the end of a word with a boolean flag to distinguish prefixes from full words.

Traverse the trie character by character for insert and search operations.

Ensure input words contain only lowercase letters or adapt the code accordingly.

Manage memory carefully in real applications to avoid leaks.