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.

What is a Trie?

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

Prefix-Based Word Storage

Imagine browsing a physical dictionary. To find words starting with "cat", you don't scan every page. You go straight to the section for 'c', then move to 'a', and then follow the letters to 't'.

A Trie (also known as a Prefix Tree or Digital Tree) is a tree-like data structure used to store a collection of strings where keys are usually strings.

Key Characteristics:

Node Representation: Each node in a Trie represents a single character, except for the root node, which is empty.
Shared Prefixes: Words with common prefixes share the same nodes (saving significant space!).
Path Association: The path from the root node down to a specific node forms a word or prefix.

Real-Life Use Cases:

Autocomplete Engines: Offering search suggestions as you type.
Spell Checkers: Checking if a word exists in a dictionary.
IP Routing: Longest prefix matching in network routers.

Why Choose Trie over HashMap?

While both offer fast lookups, Tries are superior for prefix-based queries (e.g., finding all words starting with "app"), sorting strings alphabetically, and avoiding hash collisions.

C++ Implementation — What is a Trie?

#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

Fixed Charset Optimization

Imagine an apartment corridor with exactly 26 mailboxes. When a letter arrives, you instantly drop it into the box matching character - 'a' without looking through a directory or map.

If the character set is restricted (e.g., lowercase English letters a through z), you can optimize Trie performance by replacing hash maps with fixed-size pointers arrays.

Array vs HashMap:

Array: Provides true O(1) access, but consumes fixed memory (26 pointers per node) regardless of slot utilization. Best for smaller, fixed charsets.
HashMap: Dynamically allocates memory for child nodes, but incurs overhead from hash computations. Best for large or variable charsets (like Unicode).

Common Trie Challenges:

Implement Trie: Standard insert, search, and prefix matching.
Word Search II: Searching multiple words on a grid simultaneously.
Maximum XOR of Two Numbers: Binary Trie matching.

C++ Implementation — Trie with Array (Optimized)

#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

DFS-Based Autocomplete

Imagine typing "app" in a search engine. The search box immediately shows recommendations like "apple", "apply", and "application".

How it works:

Prefix Traversal: Navigate down the Trie starting at the root, following the characters of the prefix ("app").
Downstream Search: From that node, perform a depth-first search (DFS) to collect all valid word ending markers under that branch.
Top-K Optimizations: In production, nodes often store search frequencies, allowing a min-heap to return only the Top K most popular matching words.

C++ Implementation — Autocomplete with Trie

#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

Multi-Word Grid Search

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

Why Simple DFS Fails:

Running a standard DFS from every cell for every word individually takes O(words * cells * 4^(wordLen)) time, causing Time Limit Exceeded (TLE).

Trie Optimization:

By building a Trie from the word list, we can run a single DFS from each board cell. We traverse the Trie and board path concurrently, pruning our search early the moment our current grid path does not exist in the Trie. This reduces the search space significantly.

C++ Implementation — Word Search II (LeetCode 212)

#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; }

#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; }