W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Trie (Prefix Tree)

Essential for string operations - Autocomplete, Spell Check, and Word Search.

Topics

Minutes

C++

Language

What is a Trie?

Insert: O(m) | Search: O(m) | Prefix: O(p)

A Trie (pronounced "try") is a tree-like data structure used to store a dynamic set of strings. Also called Prefix Tree or Digital Tree.

Key Characteristics:

Each node represents a character
Root node is empty
Path from root forms a word
Common prefixes share same path (saves space!)

Real-life Use Cases:

Autocomplete (Google search suggestions)
Spell Checker (Word processors)
IP Routing (Routers use tries)
Phone Directory (Contact search)
Dictionary (Word lookup)

Why Trie over HashMap?

Prefix-based search (autocomplete)
Alphabetically sorted order
No hash collisions
Efficient for string operations

Time Complexity:

Insert: O(m) where m = length of word
Search: O(m)
Prefix Search: O(p) where p = prefix length

C++ Implementation

#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() : isEndOfWord(false) {}
};

class Trie {
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    // Insert a word into Trie - O(m)
    void insert(string word) {
        TrieNode* current = root;
        for (char c : word) {
            if (current->children.find(c) == current->children.end()) {
                current->children[c] = new TrieNode();
            }
            current = current->children[c];
        }
        current->isEndOfWord = true;
    }
    
    // Search for exact word - O(m)
    bool search(string word) {
        TrieNode* current = root;
        for (char c : word) {
            if (current->children.find(c) == current->children.end()) {
                return false;
            }
            current = current->children[c];
        }
        return current->isEndOfWord;
    }
    
    // Check if any word starts with prefix - O(p)
    bool startsWith(string prefix) {
        TrieNode* current = root;
        for (char c : prefix) {
            if (current->children.find(c) == current->children.end()) {
                return false;
            }
            current = current->children[c];
        }
        return true;  // Prefix exists
    }
};

int main() {
    Trie trie;
    
    // Insert words
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("banana");
    
    // Search
    cout << "Search 'apple': " << (trie.search("apple") ? "Found" : "Not Found") << endl;
    cout << "Search 'app': " << (trie.search("app") ? "Found" : "Not Found") << endl;
    cout << "Search 'appl': " << (trie.search("appl") ? "Found" : "Not Found") << endl;
    
    // Prefix search
    cout << "Starts with 'app': " << (trie.startsWith("app") ? "Yes" : "No") << endl;
    cout << "Starts with 'ban': " << (trie.startsWith("ban") ? "Yes" : "No") << endl;
    cout << "Starts with 'cat': " << (trie.startsWith("cat") ? "Yes" : "No") << endl;
    
    return 0;
}

Trie with Array (Optimized)

All operations: O(m) where m = word length

When we know the character set is limited (e.g., lowercase a-z), we can use array-based Trie for faster access.

Array vs HashMap:

Aspect	Array	HashMap
Access Time	O(1)	O(1) average
Memory	Fixed 26 pointers	Dynamic
Best for	Known charset	Unicode/variable

Memory Optimization:

Use array when charset is small (26 for lowercase)
Use HashMap when charset is large (Unicode)

Common Interview Problems:

Implement Trie (LeetCode 208) ⭐
Word Search II (LeetCode 212) ⭐⭐⭐
Design Search Autocomplete (LeetCode 642)
Replace Words (LeetCode 648)
Maximum XOR of Two Numbers (LeetCode 421)

C++ Implementation

#include <iostream>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];  // Fixed size for a-z
    bool isEnd;
    int prefixCount;  // Count words with this prefix
    
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEnd = false;
        prefixCount = 0;
    }
};

class Trie {
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';  // Convert char to index
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
            node->prefixCount++;
        }
        node->isEnd = true;
    }
    
    bool search(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->isEnd;
    }
    
    // Count words with given prefix
    int countWithPrefix(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!node->children[index]) return 0;
            node = node->children[index];
        }
        return node->prefixCount;
    }
    
    // Delete a word
    bool deleteWord(TrieNode* node, string word, int depth = 0) {
        if (!node) return false;
        
        if (depth == word.size()) {
            if (node->isEnd) {
                node->isEnd = false;
                return true;
            }
            return false;
        }
        
        int index = word[depth] - 'a';
        if (deleteWord(node->children[index], word, depth + 1)) {
            node->prefixCount--;
            return true;
        }
        return false;
    }
    
    void deleteWord(string word) {
        deleteWord(root, word);
    }
};

int main() {
    Trie trie;
    
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("apply");
    
    cout << "Words with prefix 'app': " << trie.countWithPrefix("app") << endl;  // 4
    cout << "Words with prefix 'appl': " << trie.countWithPrefix("appl") << endl;  // 3
    
    trie.deleteWord("apple");
    cout << "After deleting 'apple':" << endl;
    cout << "Search 'apple': " << (trie.search("apple") ? "Found" : "Not Found") << endl;
    cout << "Words with prefix 'app': " << trie.countWithPrefix("app") << endl;  // Still counts prefix
    
    return 0;
}

Autocomplete with Trie

Autocomplete: O(p + n) where p = prefix length, n = matching words

Autocomplete is the classic use case for Trie. Given a prefix, return all words that start with it.

Algorithm:

Navigate to the node representing prefix
Perform DFS/BFS from that node
Collect all complete words

Optimization for Top-K Results:

Store frequency with each word
Use priority queue for top K suggestions
Pre-sort results for faster lookup

Real Applications:

Google Search suggestions
IDE code completion
Mobile keyboard predictions
E-commerce search bars

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

class AutoComplete {
    TrieNode* root;
    
    // DFS to find all words from a node
    void findAllWords(TrieNode* node, string current, vector<string>& results) {
        if (!node) return;
        if (node->isEnd) {
            results.push_back(current);
        }
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                findAllWords(node->children[i], current + char('a' + i), results);
            }
        }
    }
    
public:
    AutoComplete() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    // Get all words with given prefix
    vector<string> getSuggestions(string prefix) {
        vector<string> results;
        TrieNode* node = root;
        
        // Navigate to prefix end
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                return results;  // Prefix not found
            }
            node = node->children[idx];
        }
        
        // Find all words from this point
        findAllWords(node, prefix, results);
        return results;
    }
};

int main() {
    AutoComplete ac;
    
    // Insert dictionary words
    ac.insert("apple");
    ac.insert("app");
    ac.insert("application");
    ac.insert("apply");
    ac.insert("appreciate");
    ac.insert("banana");
    ac.insert("band");
    ac.insert("bandana");
    
    // Get suggestions
    cout << "Suggestions for 'app':" << endl;
    vector<string> suggestions = ac.getSuggestions("app");
    for (const string& s : suggestions) {
        cout << "  - " << s << endl;
    }
    
    cout << "
Suggestions for 'ban':" << endl;
    suggestions = ac.getSuggestions("ban");
    for (const string& s : suggestions) {
        cout << "  - " << s << endl;
    }
    
    return 0;
}

Word Search II (LeetCode 212)

O(rows × cols × 4^maxWordLen) with Trie pruning

Problem: Given a 2D board of characters and a list of words, find all words that exist in the board.

Approach:

Build Trie from word list
DFS from each cell on board
Check if current path exists in Trie
Prune paths that don't match any word

Why Trie here?

Without Trie: O(words × cells × 4^wordLength)
With Trie: Start DFS from cells that match Trie root
Prune early when path not in Trie

This is a HARD problem frequently asked at:

Amazon
Google
Microsoft
Meta

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    string word;  // Store complete word at end node
    
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        word = "";
    }
};

class Solution {
    TrieNode* root;
    vector<string> result;
    int rows, cols;
    
    void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node) {
        char ch = board[r][c];
        
        if (ch == '#' || !node->children[ch - 'a']) return;
        
        node = node->children[ch - 'a'];
        
        // Found a word!
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = "";  // Avoid duplicates
        }
        
        // Mark as visited
        board[r][c] = '#';
        
        // Explore 4 directions
        int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                dfs(board, nr, nc, node);
            }
        }
        
        // Restore
        board[r][c] = ch;
    }
    
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        root = new TrieNode();
        rows = board.size();
        cols = board[0].size();
        result.clear();
        
        // Build Trie from words
        for (string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                int idx = c - 'a';
                if (!node->children[idx]) {
                    node->children[idx] = new TrieNode();
                }
                node = node->children[idx];
            }
            node->word = word;  // Mark end with the word itself
        }
        
        // Start DFS from each cell
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, root);
            }
        }
        
        return result;
    }
};

int main() {
    Solution sol;
    
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath", "pea", "eat", "rain"};
    
    vector<string> found = sol.findWords(board, words);
    
    cout << "Words found in board:" << endl;
    for (const string& word : found) {
        cout << "  - " << word << endl;
    }
    
    return 0;
}

#include <iostream> #include <unordered_map> using namespace std; class TrieNode { public: unordered_map<char, TrieNode*> children; bool isEndOfWord; TrieNode() : isEndOfWord(false) {} }; class Trie { TrieNode* root; public: Trie() { root = new TrieNode(); } // Insert a word into Trie - O(m) void insert(string word) { TrieNode* current = root; for (char c : word) { if (current->children.find(c) == current->children.end()) { current->children[c] = new TrieNode(); } current = current->children[c]; } current->isEndOfWord = true; } // Search for exact word - O(m) bool search(string word) { TrieNode* current = root; for (char c : word) { if (current->children.find(c) == current->children.end()) { return false; } current = current->children[c]; } return current->isEndOfWord; } // Check if any word starts with prefix - O(p) bool startsWith(string prefix) { TrieNode* current = root; for (char c : prefix) { if (current->children.find(c) == current->children.end()) { return false; } current = current->children[c]; } return true; // Prefix exists } }; int main() { Trie trie; // Insert words trie.insert("apple"); trie.insert("app"); trie.insert("application"); trie.insert("banana"); // Search cout << "Search 'apple': " << (trie.search("apple") ? "Found" : "Not Found") << endl; cout << "Search 'app': " << (trie.search("app") ? "Found" : "Not Found") << endl; cout << "Search 'appl': " << (trie.search("appl") ? "Found" : "Not Found") << endl; // Prefix search cout << "Starts with 'app': " << (trie.startsWith("app") ? "Yes" : "No") << endl; cout << "Starts with 'ban': " << (trie.startsWith("ban") ? "Yes" : "No") << endl; cout << "Starts with 'cat': " << (trie.startsWith("cat") ? "Yes" : "No") << endl; return 0; }

Aspect

Array

HashMap

Access Time

O(1)

O(1) average

Memory

Fixed 26 pointers

Dynamic

Best for

Known charset

Unicode/variable

#include <iostream> using namespace std; class TrieNode { public: TrieNode* children[26]; // Fixed size for a-z bool isEnd; int prefixCount; // Count words with this prefix TrieNode() { for (int i = 0; i < 26; i++) { children[i] = nullptr; } isEnd = false; prefixCount = 0; } }; class Trie { TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(string word) { TrieNode* node = root; for (char c : word) { int index = c - 'a'; // Convert char to index if (!node->children[index]) { node->children[index] = new TrieNode(); } node = node->children[index]; node->prefixCount++; } node->isEnd = true; } bool search(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->isEnd; } // Count words with given prefix int countWithPrefix(string prefix) { TrieNode* node = root; for (char c : prefix) { int index = c - 'a'; if (!node->children[index]) return 0; node = node->children[index]; } return node->prefixCount; } // Delete a word bool deleteWord(TrieNode* node, string word, int depth = 0) { if (!node) return false; if (depth == word.size()) { if (node->isEnd) { node->isEnd = false; return true; } return false; } int index = word[depth] - 'a'; if (deleteWord(node->children[index], word, depth + 1)) { node->prefixCount--; return true; } return false; } void deleteWord(string word) { deleteWord(root, word); } }; int main() { Trie trie; trie.insert("apple"); trie.insert("app"); trie.insert("application"); trie.insert("apply"); cout << "Words with prefix 'app': " << trie.countWithPrefix("app") << endl; // 4 cout << "Words with prefix 'appl': " << trie.countWithPrefix("appl") << endl; // 3 trie.deleteWord("apple"); cout << "After deleting 'apple':" << endl; cout << "Search 'apple': " << (trie.search("apple") ? "Found" : "Not Found") << endl; cout << "Words with prefix 'app': " << trie.countWithPrefix("app") << endl; // Still counts prefix return 0; }

#include <iostream> #include <vector> #include <string> using namespace std; class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for (int i = 0; i < 26; i++) children[i] = nullptr; isEnd = false; } }; class AutoComplete { TrieNode* root; // DFS to find all words from a node void findAllWords(TrieNode* node, string current, vector<string>& results) { if (!node) return; if (node->isEnd) { results.push_back(current); } for (int i = 0; i < 26; i++) { if (node->children[i]) { findAllWords(node->children[i], current + char('a' + i), results); } } } public: AutoComplete() { root = new TrieNode(); } void insert(string word) { TrieNode* node = root; for (char c : word) { int idx = c - 'a'; if (!node->children[idx]) { node->children[idx] = new TrieNode(); } node = node->children[idx]; } node->isEnd = true; } // Get all words with given prefix vector<string> getSuggestions(string prefix) { vector<string> results; TrieNode* node = root; // Navigate to prefix end for (char c : prefix) { int idx = c - 'a'; if (!node->children[idx]) { return results; // Prefix not found } node = node->children[idx]; } // Find all words from this point findAllWords(node, prefix, results); return results; } }; int main() { AutoComplete ac; // Insert dictionary words ac.insert("apple"); ac.insert("app"); ac.insert("application"); ac.insert("apply"); ac.insert("appreciate"); ac.insert("banana"); ac.insert("band"); ac.insert("bandana"); // Get suggestions cout << "Suggestions for 'app':" << endl; vector<string> suggestions = ac.getSuggestions("app"); for (const string& s : suggestions) { cout << " - " << s << endl; } cout << " Suggestions for 'ban':" << endl; suggestions = ac.getSuggestions("ban"); for (const string& s : suggestions) { cout << " - " << s << endl; } return 0; }

#include <iostream> #include <vector> #include <string> using namespace std; class TrieNode { public: TrieNode* children[26]; string word; // Store complete word at end node TrieNode() { for (int i = 0; i < 26; i++) children[i] = nullptr; word = ""; } }; class Solution { TrieNode* root; vector<string> result; int rows, cols; void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node) { char ch = board[r][c]; if (ch == '#' || !node->children[ch - 'a']) return; node = node->children[ch - 'a']; // Found a word! if (!node->word.empty()) { result.push_back(node->word); node->word = ""; // Avoid duplicates } // Mark as visited board[r][c] = '#'; // Explore 4 directions int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; for (auto& d : dirs) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) { dfs(board, nr, nc, node); } } // Restore board[r][c] = ch; } public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { root = new TrieNode(); rows = board.size(); cols = board[0].size(); result.clear(); // Build Trie from words for (string& word : words) { TrieNode* node = root; for (char c : word) { int idx = c - 'a'; if (!node->children[idx]) { node->children[idx] = new TrieNode(); } node = node->children[idx]; } node->word = word; // Mark end with the word itself } // Start DFS from each cell for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { dfs(board, i, j, root); } } return result; } }; int main() { Solution sol; vector<vector<char>> board = { {'o','a','a','n'}, {'e','t','a','e'}, {'i','h','k','r'}, {'i','f','l','v'} }; vector<string> words = {"oath", "pea", "eat", "rain"}; vector<string> found = sol.findWords(board, words); cout << "Words found in board:" << endl; for (const string& word : found) { cout << " - " << word << endl; } return 0; }