When I first started working with prefix trees—or Tries—I fell into a trap that almost every developer does. I thought of a Trie as just a "tree of characters," so I designed my nodes to actually store the character they represented. I'd create a Node struct with a char value field, thinking it was the logical way to keep track of where I was in a word.

Stop Storing Characters Inside Your Nodes

Here is why that approach is a waste of time and memory: if you store the character 'a' inside the node, you still need a way to find that node from the parent. You'll end up writing a loop to search through a list of children to find the one where node->value == 'a'. This turns your O(L) lookup (where L is the word length) into something much slower, effectively defeating the purpose of the Trie.

In a properly implemented Trie, the character isn't in the node; the character is the edge you took to get there. If you have an array of 26 pointers in your node, the fact that you followed the pointer at index 0 tells you that you've encountered an 'a'. The node itself is just a destination that says, "You've reached this point in the prefix; now where to next?"

Mapping the Alphabet to Array Indices

To make this work, we use a simple mapping. For lowercase English letters, index = character - 'a'. This gives us a direct O(1) jump to the next node. I've found that using std::unique_ptr here is a lifesaver. If you use raw pointers, you'll spend half your time writing a recursive destructor to avoid massive memory leaks every time a Trie goes out of scope.

#include <iostream>
#include <vector>
#include <memory>
#include <string>

struct TrieNode {
    // We use a fixed-size array for the English alphabet
    std::unique_ptr<TrieNode> children[26];
    bool isEndOfWord = false;

    TrieNode() {
        // unique_ptr initializes to nullptr by default, 
        // so no need for a manual loop here.
    }
};

class Trie {
private:
    std::unique_ptr<TrieNode> root;

public:
    Trie() : root(std::make_unique<TrieNode>()) {}

    void insert(const std::string& word) {
        TrieNode* current = root.get();
        for (char ch : word) {
            int index = ch - 'a';
            if (!current->children[index]) {
                current->children[index] = std::make_unique<TrieNode>();
            }
            current = current->children[index].get();
        }
        current->isEndOfWord = true;
    }

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

Handling the "Prefix" in Prefix Tree

The real power of the Trie isn't just searching for whole words—it's the startsWith functionality. Because of the structure we just built, checking if any word in your dictionary starts with "app" is exactly the same as searching for the word "app", except you don't care about the isEndOfWord flag at the end. You just care if you successfully navigated the path.

I've seen people try to implement this using std::map<char, TrieNode*> instead of a fixed array. That's a valid trade-off. If you're supporting the entire Unicode set, a 26-slot array is useless, and a map prevents your memory usage from exploding. But for a standard A-Z set, the array is significantly faster because it avoids the overhead of map balancing and hashing.

📋 Practical Task

Build a Case-Insensitive Autocomplete Suggestion Engine

Your task is to extend the Trie implementation provided in the lesson to support a full autocomplete feature. Instead of just returning a boolean for search, you need to implement a method that returns all words in the Trie that start with a given prefix.

Requirements:

• Implement a method std::vector<std::string> getSuggestions(std::string prefix).
• The method should first navigate to the node representing the end of the prefix.
• From that node, perform a depth-first search (DFS) to find all possible complete words that branch off from that prefix.
• Ensure the implementation is case-insensitive (treat 'A' and 'a' as the same index).
• Test your engine with a dictionary containing: "apple", "apply", "appetizer", "ball", "bat", "batch". Searching for "app" should return "apple", "apply", "appetizer".