Trie (Prefix Tree)

Learn about the Trie data structure and its applications in string processing and dictionary problems.

Trie Fundamentals

What is a Trie?

A Trie (pronounced "try") is a tree-like data structure that stores strings in a way that makes prefix-based operations efficient. Each node represents a character, and paths from root to leaf represent complete strings.

Basic Structure

class TrieNode {
public:
    TrieNode* children[26];  // For lowercase English letters
    bool isEndOfWord;
    
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
    }
};

Trie Class Implementation

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    // Insert a word into the trie
    void insert(string word) {
        TrieNode* current = root;
        
        for (char c : word) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        
        current->isEndOfWord = true;
    }
    
    // Search for a word in the trie
    bool search(string word) {
        TrieNode* current = root;
        
        for (char c : word) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                return false;
            }
            current = current->children[index];
        }
        
        return current->isEndOfWord;
    }
    
    // Check if any word starts with the given prefix
    bool startsWith(string prefix) {
        TrieNode* current = root;
        
        for (char c : prefix) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                return false;
            }
            current = current->children[index];
        }
        
        return true;
    }
};

String Prefix Problems

Longest Common Prefix

// Find the longest common prefix of all strings
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    
    string prefix = strs[0];
    
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.length() - 1);
            if (prefix.empty()) return "";
        }
    }
    
    return prefix;
}

Prefix Matching

// Find all words that start with a given prefix
vector<string> findWordsWithPrefix(TrieNode* root, string prefix) {
    vector<string> result;
    TrieNode* current = root;
    
    // Navigate to the prefix node
    for (char c : prefix) {
        int index = c - 'a';
        if (current->children[index] == nullptr) {
            return result; // No words with this prefix
        }
        current = current->children[index];
    }
    
    // DFS to find all words starting from this node
    dfs(current, prefix, result);
    return result;
}

void dfs(TrieNode* node, string currentWord, vector<string>& result) {
    if (node->isEndOfWord) {
        result.push_back(currentWord);
    }
    
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != nullptr) {
            char c = 'a' + i;
            dfs(node->children[i], currentWord + c, result);
        }
    }
}

Word Search

Word Search in 2D Grid

// Check if a word exists in a 2D grid using Trie
bool wordSearch(vector<vector<char>>& board, vector<string>& words) {
    Trie trie;
    for (string word : words) {
        trie.insert(word);
    }
    
    int m = board.size();
    int n = board[0].size();
    vector<string> result;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(board, i, j, trie.root, "", result);
        }
    }
    
    return !result.empty();
}

void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, 
         string word, vector<string>& result) {
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
        return;
    }
    
    char c = board[i][j];
    if (c == '#' || node->children[c - 'a'] == nullptr) {
        return;
    }
    
    node = node->children[c - 'a'];
    word += c;
    
    if (node->isEndOfWord) {
        result.push_back(word);
        node->isEndOfWord = false; // Avoid duplicates
    }
    
    board[i][j] = '#'; // Mark as visited
    
    // Explore all four directions
    dfs(board, i + 1, j, node, word, result);
    dfs(board, i - 1, j, node, word, result);
    dfs(board, i, j + 1, node, word, result);
    dfs(board, i, j - 1, node, word, result);
    
    board[i][j] = c; // Restore
}

Autocomplete

Autocomplete System

class AutocompleteSystem {
private:
    TrieNode* root;
    string currentQuery;
    
public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        root = new TrieNode();
        for (int i = 0; i < sentences.size(); i++) {
            insertWithFrequency(sentences[i], times[i]);
        }
    }
    
    void insertWithFrequency(string sentence, int frequency) {
        TrieNode* current = root;
        
        for (char c : sentence) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        
        current->isEndOfWord = true;
        current->frequency = frequency;
    }
    
    vector<string> input(char c) {
        if (c == '#') {
            insertWithFrequency(currentQuery, 1);
            currentQuery = "";
            return {};
        }
        
        currentQuery += c;
        return getTopSuggestions(currentQuery, 3);
    }
    
    vector<string> getTopSuggestions(string prefix, int k) {
        vector<pair<string, int>> suggestions;
        TrieNode* current = root;
        
        // Navigate to prefix node
        for (char c : prefix) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                return {};
            }
            current = current->children[index];
        }
        
        // Collect all suggestions
        collectSuggestions(current, prefix, suggestions);
        
        // Sort by frequency and return top k
        sort(suggestions.begin(), suggestions.end(), 
             [](const pair<string, int>& a, const pair<string, int>& b) {
                 return a.second > b.second;
             });
        
        vector<string> result;
        for (int i = 0; i < min(k, (int)suggestions.size()); i++) {
            result.push_back(suggestions[i].first);
        }
        
        return result;
    }
};

Dictionary Problems

Word Break

// Check if a string can be segmented into dictionary words
bool wordBreak(string s, vector<string>& wordDict) {
    Trie trie;
    for (string word : wordDict) {
        trie.insert(word);
    }
    
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && trie.search(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n];
}

Word Break II

// Find all possible sentences from word break
vector<string> wordBreakII(string s, vector<string>& wordDict) {
    Trie trie;
    for (string word : wordDict) {
        trie.insert(word);
    }
    
    vector<string> result;
    vector<string> current;
    
    dfs(s, 0, trie.root, current, result);
    return result;
}

void dfs(string s, int start, TrieNode* root, vector<string>& current, 
         vector<string>& result) {
    if (start == s.length()) {
        string sentence = "";
        for (int i = 0; i < current.size(); i++) {
            if (i > 0) sentence += " ";
            sentence += current[i];
        }
        result.push_back(sentence);
        return;
    }
    
    TrieNode* current = root;
    for (int i = start; i < s.length(); i++) {
        int index = s[i] - 'a';
        if (current->children[index] == nullptr) {
            break;
        }
        
        current = current->children[index];
        if (current->isEndOfWord) {
            current.push_back(s.substr(start, i - start + 1));
            dfs(s, i + 1, root, current, result);
            current.pop_back();
        }
    }
}

Advanced Trie Operations

Trie with Frequency

class TrieNodeWithFreq {
public:
    TrieNodeWithFreq* children[26];
    bool isEndOfWord;
    int frequency;
    
    TrieNodeWithFreq() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
        frequency = 0;
    }
};

Trie with Deletion

// Delete a word from the trie
bool deleteWord(TrieNode* root, string word, int index = 0) {
    if (index == word.length()) {
        if (!root->isEndOfWord) return false;
        root->isEndOfWord = false;
        return isEmpty(root);
    }
    
    int charIndex = word[index] - 'a';
    if (root->children[charIndex] == nullptr) return false;
    
    bool shouldDelete = deleteWord(root->children[charIndex], word, index + 1);
    
    if (shouldDelete) {
        delete root->children[charIndex];
        root->children[charIndex] = nullptr;
        return isEmpty(root) && !root->isEndOfWord;
    }
    
    return false;
}

bool isEmpty(TrieNode* node) {
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != nullptr) {
            return false;
        }
    }
    return true;
}

Performance Analysis

Time Complexity

Insert: O(m) where m is the length of the word
Search: O(m) where m is the length of the word
Prefix Search: O(m) where m is the length of the prefix
Space: O(ALPHABET_SIZE * N * M) where N is the number of words and M is the average length

Space Optimization

Compressed Trie: Merge nodes with single children
Ternary Search Tree: Alternative to trie with less space
Suffix Tree: For suffix-based operations

Common Patterns

String matching and prefix operations
Autocomplete and suggestion systems
Word games and puzzles
Dictionary operations and text processing
Pattern matching in strings

Applications

Search engines: Autocomplete and suggestion
Spell checkers: Dictionary lookup
IP routing: Longest prefix matching
Bioinformatics: DNA sequence analysis
Text editors: Code completion

Trie Fundamentals​

What is a Trie?​

Basic Structure​

Trie Class Implementation​

String Prefix Problems​

Longest Common Prefix​

Prefix Matching​

Word Search​

Word Search in 2D Grid​

Autocomplete​

Autocomplete System​

Dictionary Problems​

Word Break​

Word Break II​

Advanced Trie Operations​

Trie with Frequency​

Trie with Deletion​

Performance Analysis​

Time Complexity​

Space Optimization​

Common Patterns​

Applications​