Trie (Prefix Tree)

A Trie is a tree-like data structure used to store and search strings efficiently. Each node represents a character, and paths from root to node represent prefixes.

When to Use

Autocomplete or search suggestions
Spell checkers and dictionary lookups
IP routing tables
Problems with prefix matching or string searches

Common Patterns

Standard Trie

Insert and search words with prefix matching

Example: Implement Trie, word search II

Trie with Additional Data

Store extra information at nodes (counts, indices)

Example: Word frequency, autocomplete with ranking

Code Templates

Python

class TrieNode:
    def __init__(self):
        self.children = {}  # or [None] * 26 for lowercase
        self.is_end_of_word = False
        self.word = None  # Optional: store complete word

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Insert a word into the trie"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
        node.word = word
    
    def search(self, word):
        """Search for exact word"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word
    
    def starts_with(self, prefix):
        """Check if any word starts with prefix"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def find_words_with_prefix(self, prefix):
        """Find all words with given prefix"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        # DFS to find all words from this node
        result = []
        def dfs(node):
            if node.is_end_of_word:
                result.append(node.word)
            for child in node.children.values():
                dfs(child)
        
        dfs(node)
        return result

C++

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    // Or: TrieNode* children[26] = {}; for lowercase only
    bool isEndOfWord = false;
    string word = "";  // Optional: store complete word
};

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    // Insert a word into the trie
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
        node->word = word;
    }
    
    // Search for exact word
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEndOfWord;
    }
    
    // Check if any word starts with prefix
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
    
    // Find all words with given prefix
    vector<string> findWordsWithPrefix(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return {};
            }
            node = node->children[c];
        }
        
        // DFS to find all words from this node
        vector<string> result;
        function<void(TrieNode*)> dfs = [&](TrieNode* node) {
            if (node->isEndOfWord) {
                result.push_back(node->word);
            }
            for (auto& [c, child] : node->children) {
                dfs(child);
            }
        };
        
        dfs(node);
        return result;
    }
};