Report Content

Trie Data Structure: Prefix Trees & Applications

Master trie operations, pattern matching, and autocomplete implementations. This tutorial covers trie structure, insertion/search algorithms, and real-world applications with coding examples.

Trie Usage in Applications (2023)

Autocomplete (40%)

Spell Checkers (30%)

IP Routing (20%)

Other (10%)

1. Trie Fundamentals

Trie (Prefix Tree)

Definition

Trie (Digital Tree or Prefix Tree) is an ordered tree data structure used to store a dynamic set of strings. Each node represents a character, and paths from root to leaf form words. Common prefixes are shared, making it efficient for prefix-based operations.

How It Works

Insert Operation

Start from root node
For each character, traverse or create child node
Mark last node as end of word (isEndOfWord = true)

Search Operation

Traverse nodes following characters
If any character missing → word doesn't exist
Check isEndOfWord flag at final node

Prefix Search

Same traversal as search
Don't need isEndOfWord flag
Returns true if prefix exists

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        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
    
    def search(self, word: str) -> bool:
        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: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    
    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }
    
    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return node.isEndOfWord;
    }
    
    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return true;
    }
}

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;
    
    TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return true;
    }
}

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

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

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    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;
    }
    
    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;
    }
    
    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;
    }
};

Complexity: Insert O(L), Search O(L), Prefix O(P) where L = word length
Space: O(total characters across all words)
Use When: Prefix matching, autocomplete, dictionary storage

2. Autocomplete & Prefix Search

Autocomplete (Word Suggestions)

Definition

Autocomplete returns all words in the trie that start with a given prefix. It's used in search engines, text editors, and command-line interfaces to suggest completions as the user types.

How It Works

Navigate to prefix node

Traverse the trie following prefix characters
If any character missing, return empty list

DFS traversal from prefix node

Perform depth-first search from current node
Collect all paths where isEndOfWord is true

Return suggestions

Build full words by tracking path characters
Return list of matching words

def get_suggestions(self, prefix):
    node = self.root
    # Navigate to prefix node
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
    
    # DFS to collect all words
    suggestions = []
    self._dfs(node, prefix, suggestions)
    return suggestions

def _dfs(self, node, current_word, suggestions):
    if node.is_end_of_word:
        suggestions.append(current_word)
    
    for char, child_node in node.children.items():
        self._dfs(child_node, current_word + char, suggestions)

# Usage
trie = Trie()
words = ["apple", "application", "apply", "apt", "cat", "car"]
for word in words:
    trie.insert(word)

suggestions = get_suggestions("ap")  # Returns ["apple", "application", "apply"]

getSuggestions(prefix) {
    let node = this.root;
    // Navigate to prefix node
    for (const char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    
    const suggestions = [];
    this._dfs(node, prefix, suggestions);
    return suggestions;
}

_dfs(node, currentWord, suggestions) {
    if (node.isEndOfWord) {
        suggestions.push(currentWord);
    }
    
    for (const [char, childNode] of Object.entries(node.children)) {
        this._dfs(childNode, currentWord + char, suggestions);
    }
}

// Usage
const trie = new Trie();
const words = ["apple", "application", "apply", "apt", "cat", "car"];
words.forEach(word => trie.insert(word));

const suggestions = trie.getSuggestions("ap"); 
// Returns ["apple", "application", "apply"]

public List<String> getSuggestions(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            return new ArrayList<>();
        }
        node = node.children[index];
    }
    
    List<String> suggestions = new ArrayList<>();
    dfs(node, prefix, suggestions);
    return suggestions;
}

private void dfs(TrieNode node, String currentWord, List<String> suggestions) {
    if (node.isEndOfWord) {
        suggestions.add(currentWord);
    }
    
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            char c = (char) ('a' + i);
            dfs(node.children[i], currentWord + c, suggestions);
        }
    }
}

vector<string> getSuggestions(string prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        if (node->children.find(c) == node->children.end()) {
            return {};
        }
        node = node->children[c];
    }
    
    vector<string> suggestions;
    dfs(node, prefix, suggestions);
    return suggestions;
}

void dfs(TrieNode* node, string currentWord, vector<string>& suggestions) {
    if (node->isEndOfWord) {
        suggestions.push_back(currentWord);
    }
    
    for (auto& [c, childNode] : node->children) {
        dfs(childNode, currentWord + c, suggestions);
    }
}

Complexity: O(P + W) where P = prefix length, W = total characters in matching words
Use When: Search bars, typeahead, command suggestions

3. Longest Common Prefix

Longest Common Prefix Using Trie

Definition

Longest Common Prefix (LCP) finds the longest string that is a prefix of all words in a list. Using a trie, we traverse until we reach a node with multiple children or a word ending.

How It Works

Insert all words into trie

Build trie containing all words
Common prefixes will share nodes

Traverse from root

Start with empty prefix string
Continue while node has exactly one child
Stop if node is end of a word or has multiple children

Build and return LCP

Append each character as we traverse
Return accumulated prefix

def longest_common_prefix(words):
    if not words:
        return ""
    
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    lcp = []
    node = trie.root
    
    # Traverse while single child and not end of word
    while len(node.children) == 1 and not node.is_end_of_word:
        char = next(iter(node.children))
        lcp.append(char)
        node = node.children[char]
    
    return ''.join(lcp)

# Example
words = ["flower", "flow", "flight"]
result = longest_common_prefix(words)  # Returns "fl"

function longestCommonPrefix(words) {
    if (!words.length) return "";
    
    const trie = new Trie();
    words.forEach(word => trie.insert(word));
    
    let lcp = "";
    let node = trie.root;
    
    // Traverse while single child and not end of word
    while (Object.keys(node.children).length === 1 && !node.isEndOfWord) {
        const char = Object.keys(node.children)[0];
        lcp += char;
        node = node.children[char];
    }
    
    return lcp;
}

// Example
const words = ["flower", "flow", "flight"];
const result = longestCommonPrefix(words); // Returns "fl"

public static String longestCommonPrefix(String[] words) {
    if (words.length == 0) return "";
    
    Trie trie = new Trie();
    for (String word : words) {
        trie.insert(word);
    }
    
    StringBuilder lcp = new StringBuilder();
    TrieNode node = trie.root;
    
    while (node != null) {
        int childCount = 0;
        int childIndex = -1;
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                childCount++;
                childIndex = i;
            }
        }
        
        if (childCount != 1 || node.isEndOfWord) break;
        
        lcp.append((char)('a' + childIndex));
        node = node.children[childIndex];
    }
    
    return lcp.toString();
}

string longestCommonPrefix(vector<string>& words) {
    if (words.empty()) return "";
    
    Trie trie;
    for (const string& word : words) {
        trie.insert(word);
    }
    
    string lcp = "";
    TrieNode* node = trie.root;
    
    while (node->children.size() == 1 && !node->isEndOfWord) {
        char c = node->children.begin()->first;
        lcp += c;
        node = node->children.begin()->second;
    }
    
    return lcp;
}

Complexity: O(N × L) where N = number of words, L = average length
Use When: Finding common prefixes in word lists

4. Delete Operation

Trie Deletion

Definition

Delete Operation removes a word from the trie. It must handle three cases: word is a prefix of another word, word shares prefix with others, or word has unique path. Careful cleanup prevents memory leaks.

How It Works

Traverse to word end

Check if word exists in trie
If not found, return false

Unmark end of word

Set isEndOfWord = false at final node
If node has children, we're done

Backtrack and delete

Recursively delete nodes with no children
Stop when encountering node with multiple children

def delete(self, word):
    return self._delete(self.root, word, 0)

def _delete(self, node, word, index):
    if index == len(word):
        if not node.is_end_of_word:
            return False
        node.is_end_of_word = False
        return len(node.children) == 0
    
    char = word[index]
    if char not in node.children:
        return False
    
    should_delete_child = self._delete(node.children[char], word, index + 1)
    
    if should_delete_child:
        del node.children[char]
        return len(node.children) == 0 and not node.is_end_of_word
    
    return False

delete(word) {
    return this._delete(this.root, word, 0);
}

_delete(node, word, index) {
    if (index === word.length) {
        if (!node.isEndOfWord) return false;
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0;
    }
    
    const char = word[index];
    if (!node.children[char]) return false;
    
    const shouldDelete = this._delete(node.children[char], word, index + 1);
    
    if (shouldDelete) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }
    
    return false;
}

public boolean delete(String word) {
    return delete(root, word, 0);
}

private boolean delete(TrieNode node, String word, int index) {
    if (index == word.length()) {
        if (!node.isEndOfWord) return false;
        node.isEndOfWord = false;
        
        // Check if node has no children
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) return false;
        }
        return true;
    }
    
    int charIndex = word.charAt(index) - 'a';
    if (node.children[charIndex] == null) return false;
    
    boolean shouldDelete = delete(node.children[charIndex], word, index + 1);
    
    if (shouldDelete) {
        node.children[charIndex] = null;
        
        // Check if node has any other children or is end of word
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) return false;
        }
        return !node.isEndOfWord;
    }
    
    return false;
}

bool deleteWord(string word) {
    return _delete(root, word, 0);
}

bool _delete(TrieNode* node, string word, int index) {
    if (index == word.length()) {
        if (!node->isEndOfWord) return false;
        node->isEndOfWord = false;
        return node->children.empty();
    }
    
    char c = word[index];
    if (node->children.find(c) == node->children.end()) {
        return false;
    }
    
    bool shouldDelete = _delete(node->children[c], word, index + 1);
    
    if (shouldDelete) {
        delete node->children[c];
        node->children.erase(c);
        return node->children.empty() && !node->isEndOfWord;
    }
    
    return false;
}

Complexity: O(L) where L = word length
Use When: Removing words from dictionary

5. Advanced Trie Variants

Binary Trie

Definition

Binary Trie stores binary representations of numbers, with each node having two children (0 and 1). It's optimal for maximum XOR problems and bit manipulation.

How It Works

Insert number bits

Traverse bits from most significant to least
Create child nodes for 0 and 1 paths

Find max XOR

For each number, try opposite bits at each level
Maximize XOR value

class BinaryTrieNode:
    def __init__(self):
        self.children = [None, None]

class BinaryTrie:
    def __init__(self):
        self.root = BinaryTrieNode()
    
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = BinaryTrieNode()
            node = node.children[bit]
    
    def max_xor(self, num):
        node = self.root
        result = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            # Try opposite bit for max XOR
            desired = 1 - bit
            if node.children[desired]:
                result |= (1 << i)
                node = node.children[desired]
            else:
                node = node.children[bit]
        return result

# Find maximum XOR of any two numbers
def find_max_xor(nums):
    trie = BinaryTrie()
    max_xor = 0
    for num in nums:
        trie.insert(num)
        max_xor = max(max_xor, trie.max_xor(num))
    return max_xor

class BinaryTrieNode {
    constructor() {
        this.children = [null, null];
    }
}

class BinaryTrie {
    constructor() {
        this.root = new BinaryTrieNode();
    }
    
    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!node.children[bit]) {
                node.children[bit] = new BinaryTrieNode();
            }
            node = node.children[bit];
        }
    }
    
    maxXor(num) {
        let node = this.root;
        let result = 0;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const desired = 1 - bit;
            if (node.children[desired]) {
                result |= (1 << i);
                node = node.children[desired];
            } else {
                node = node.children[bit];
            }
        }
        return result;
    }
}

function findMaxXor(nums) {
    const trie = new BinaryTrie();
    let maxXor = 0;
    for (const num of nums) {
        trie.insert(num);
        maxXor = Math.max(maxXor, trie.maxXor(num));
    }
    return maxXor;
}

class BinaryTrieNode {
    BinaryTrieNode[] children = new BinaryTrieNode[2];
}

class BinaryTrie {
    private BinaryTrieNode root = new BinaryTrieNode();
    
    public void insert(int num) {
        BinaryTrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new BinaryTrieNode();
            }
            node = node.children[bit];
        }
    }
    
    public int maxXor(int num) {
        BinaryTrieNode node = root;
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int desired = 1 - bit;
            if (node.children[desired] != null) {
                result |= (1 << i);
                node = node.children[desired];
            } else {
                node = node.children[bit];
            }
        }
        return result;
    }
}

struct BinaryTrieNode {
    BinaryTrieNode* children[2];
    BinaryTrieNode() {
        children[0] = children[1] = nullptr;
    }
};

class BinaryTrie {
private:
    BinaryTrieNode* root;
    
public:
    BinaryTrie() { root = new BinaryTrieNode(); }
    
    void insert(int num) {
        BinaryTrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new BinaryTrieNode();
            }
            node = node->children[bit];
        }
    }
    
    int maxXor(int num) {
        BinaryTrieNode* node = root;
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int desired = 1 - bit;
            if (node->children[desired]) {
                result |= (1 << i);
                node = node->children[desired];
            } else {
                node = node->children[bit];
            }
        }
        return result;
    }
};

Use When: Maximum XOR problems, bit manipulation
Complexity: O(32) per operation

6. Real-World Applications

Search Engine Autocomplete

Prefix-based suggestions: Google, Bing typeahead

class SearchEngine:
    def __init__(self):
        self.trie = Trie()
        self.popularity = {}
    
    def index_page(self, keyword, score):
        self.trie.insert(keyword)
        self.popularity[keyword] = score
    
    def autocomplete(self, prefix, limit=10):
        words = self.trie.get_suggestions(prefix)
        return sorted(words, key=lambda x: self.popularity.get(x, 0), 
                     reverse=True)[:limit]

class SearchEngine {
    constructor() {
        this.trie = new Trie();
        this.popularity = new Map();
    }
    
    indexPage(keyword, score) {
        this.trie.insert(keyword);
        this.popularity.set(keyword, score);
    }
    
    autocomplete(prefix, limit = 10) {
        const words = this.trie.getSuggestions(prefix);
        return words
            .sort((a, b) => this.popularity.get(b) - this.popularity.get(a))
            .slice(0, limit);
    }
}

class SearchEngine {
    private Trie trie;
    private Map<String, Integer> popularity;
    
    public void indexPage(String keyword, int score) {
        trie.insert(keyword);
        popularity.put(keyword, score);
    }
    
    public List<String> autocomplete(String prefix, int limit) {
        List<String> words = trie.getSuggestions(prefix);
        return words.stream()
            .sorted((a, b) -> popularity.get(b) - popularity.get(a))
            .limit(limit)
            .collect(Collectors.toList());
    }
}

class SearchEngine {
private:
    Trie trie;
    unordered_map<string, int> popularity;
    
public:
    void indexPage(string keyword, int score) {
        trie.insert(keyword);
        popularity[keyword] = score;
    }
    
    vector<string> autocomplete(string prefix, int limit = 10) {
        vector<string> words = trie.getSuggestions(prefix);
        sort(words.begin(), words.end(), [&](const string& a, const string& b) {
            return popularity[a] > popularity[b];
        });
        if (words.size() > limit) words.resize(limit);
        return words;
    }
};

Spell Checker

Dictionary lookup: Check if word exists, suggest corrections

class SpellChecker:
    def __init__(self):
        self.trie = Trie()
    
    def load_dictionary(self, words):
        for word in words:
            self.trie.insert(word.lower())
    
    def check(self, word):
        return self.trie.search(word.lower())
    
    def suggest(self, word):
        # Find words with edit distance 1
        suggestions = []
        word = word.lower()
        letters = 'abcdefghijklmnopqrstuvwxyz'
        
        # Generate possible corrections
        for i in range(len(word) + 1):
            # Insertions
            for c in letters:
                candidate = word[:i] + c + word[i:]
                if self.trie.search(candidate):
                    suggestions.append(candidate)
            
            # Deletions
            if i < len(word):
                candidate = word[:i] + word[i+1:]
                if self.trie.search(candidate):
                    suggestions.append(candidate)
            
            # Replacements
            if i < len(word):
                for c in letters:
                    candidate = word[:i] + c + word[i+1:]
                    if self.trie.search(candidate):
                        suggestions.append(candidate)
        
        return list(set(suggestions))[:10]

class SpellChecker {
    constructor() {
        this.trie = new Trie();
    }
    
    loadDictionary(words) {
        words.forEach(word => this.trie.insert(word.toLowerCase()));
    }
    
    check(word) {
        return this.trie.search(word.toLowerCase());
    }
    
    suggest(word) {
        const suggestions = new Set();
        const letters = 'abcdefghijklmnopqrstuvwxyz';
        const w = word.toLowerCase();
        
        // Generate edit distance 1 variations
        for (let i = 0; i <= w.length; i++) {
            // Insertions
            for (const c of letters) {
                const candidate = w.slice(0, i) + c + w.slice(i);
                if (this.trie.search(candidate)) suggestions.add(candidate);
            }
            
            // Deletions
            if (i < w.length) {
                const candidate = w.slice(0, i) + w.slice(i + 1);
                if (this.trie.search(candidate)) suggestions.add(candidate);
            }
            
            // Replacements
            if (i < w.length) {
                for (const c of letters) {
                    const candidate = w.slice(0, i) + c + w.slice(i + 1);
                    if (this.trie.search(candidate)) suggestions.add(candidate);
                }
            }
        }
        
        return Array.from(suggestions).slice(0, 10);
    }
}

class SpellChecker {
    private Trie trie;
    
    public SpellChecker() {
        trie = new Trie();
    }
    
    public void loadDictionary(String[] words) {
        for (String word : words) {
            trie.insert(word.toLowerCase());
        }
    }
    
    public boolean check(String word) {
        return trie.search(word.toLowerCase());
    }
}

class SpellChecker {
private:
    Trie trie;
    
public:
    void loadDictionary(vector<string>& words) {
        for (const string& word : words) {
            trie.insert(word);
        }
    }
    
    bool check(string word) {
        transform(word.begin(), word.end(), word.begin(), ::tolower);
        return trie.search(word);
    }
};

IP Routing (Longest Prefix Match)

Network routing tables: Find most specific route

class IPRoutingTable:
    def __init__(self):
        self.trie = {}
    
    def binary_str(self, ip):
        return ''.join(f'{int(octet):08b}' for octet in ip.split('.'))
    
    def add_route(self, network, mask_len, next_hop):
        bits = self.binary_str(network)[:mask_len]
        node = self.trie
        for bit in bits:
            if bit not in node:
                node[bit] = {}
            node = node[bit]
        node['next_hop'] = next_hop
    
    def lookup(self, ip):
        bits = self.binary_str(ip)
        node = self.trie
        last_hop = None
        
        for bit in bits:
            if bit not in node:
                break
            node = node[bit]
            if 'next_hop' in node:
                last_hop = node['next_hop']
        
        return last_hop

class IPRoutingTable {
    constructor() {
        this.trie = {};
    }
    
    binaryStr(ip) {
        return ip.split('.').map(octet => 
            parseInt(octet).toString(2).padStart(8, '0')
        ).join('');
    }
    
    addRoute(network, maskLen, nextHop) {
        const bits = this.binaryStr(network).slice(0, maskLen);
        let node = this.trie;
        for (const bit of bits) {
            if (!node[bit]) node[bit] = {};
            node = node[bit];
        }
        node.nextHop = nextHop;
    }
    
    lookup(ip) {
        const bits = this.binaryStr(ip);
        let node = this.trie;
        let lastHop = null;
        
        for (const bit of bits) {
            if (!node[bit]) break;
            node = node[bit];
            if (node.nextHop) lastHop = node.nextHop;
        }
        
        return lastHop;
    }
}

class IPRoutingTable {
    private Map<String, Object> trie;
    
    public IPRoutingTable() {
        trie = new HashMap<>();
    }
    
    private String binaryStr(String ip) {
        StringBuilder sb = new StringBuilder();
        for (String octet : ip.split("\\.")) {
            int val = Integer.parseInt(octet);
            sb.append(String.format("%8s", Integer.toBinaryString(val))
                     .replace(' ', '0'));
        }
        return sb.toString();
    }
    
    @SuppressWarnings("unchecked")
    public void addRoute(String network, int maskLen, String nextHop) {
        String bits = binaryStr(network).substring(0, maskLen);
        Map<String, Object> node = trie;
        for (char c : bits.toCharArray()) {
            String bit = String.valueOf(c);
            if (!node.containsKey(bit)) {
                node.put(bit, new HashMap<String, Object>());
            }
            node = (Map<String, Object>) node.get(bit);
        }
        node.put("nextHop", nextHop);
    }
}

class IPRoutingTable {
private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        string nextHop;
    };
    
    TrieNode* root;
    
    string binaryStr(string ip) {
        string result;
        stringstream ss(ip);
        string octet;
        while (getline(ss, octet, '.')) {
            int val = stoi(octet);
            result += bitset<8>(val).to_string();
        }
        return result;
    }
    
public:
    IPRoutingTable() { root = new TrieNode(); }
    
    void addRoute(string network, int maskLen, string nextHop) {
        string bits = binaryStr(network).substr(0, maskLen);
        TrieNode* node = root;
        for (char bit : bits) {
            if (node->children.find(bit) == node->children.end()) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
        node->nextHop = nextHop;
    }
};

Trie Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Word Search II (Board)	Trie + Backtracking/Traversal)	O(M × 4 × 3^(L-1)))
Replace Words (Prefix replacement)	Trie prefix matching + substitution)	O(N × L) (where N = words, L = length)
Concatenated Words (Multi-word combo)	Trie with DFS + memoization)	O(N × L²) (where N = words, L = length)
Maximum XOR of Two Numbers)	Binary Trie (bit-by-bit traversal)	O(N × 32) (optimal for integers)
Longest Common Prefix)	Trie with single child traversal)	O(N × L) (efficient prefix detection)
Pattern Matching (Wildcard)	Trie with DFS + wildcard handling)	O(26^K) (where K = wildcard count)

Trie Implementation Checklist

Use array for children when alphabet is fixed (26 letters)

Use hash map for Unicode or large character sets

Track word count/end at each node for deletion

Consider compressed/radix tries for memory optimization

Add frequency counters for autocomplete ranking

Handle case sensitivity based on requirements

Implement iterative DFS instead of recursive for deep tries

DSA Expert Insight: Trie problems appear in 15% of technical interviews, especially in search-related and prefix matching scenarios. Mastering both basic operations and specialized trie variants is crucial for efficient string manipulation problems. For production systems, combine tries with caches (e.g., Redis) for popular prefixes and use Ternary Search Tries for better space efficiency when dealing with large character sets.

You need to be logged in to participate in this discussion.

Report Content

Trie Data Structure: Prefix Trees & Applications

Trie Usage in Applications (2023)

1. Trie Fundamentals

Trie (Prefix Tree)

Definition

How It Works

Insert Operation

Search Operation

Prefix Search

2. Autocomplete & Prefix Search

Autocomplete (Word Suggestions)

Definition

How It Works

Navigate to prefix node

DFS traversal from prefix node

Return suggestions

3. Longest Common Prefix

Longest Common Prefix Using Trie

Definition

How It Works

Insert all words into trie

Traverse from root

Build and return LCP

4. Delete Operation

Trie Deletion

Definition

How It Works

Traverse to word end

Unmark end of word

Backtrack and delete

5. Advanced Trie Variants

Binary Trie

Definition

How It Works

Insert number bits

Find max XOR

6. Real-World Applications

Search Engine Autocomplete

Spell Checker

IP Routing (Longest Prefix Match)

Trie Problem-Solving Cheat Sheet

Trie Implementation Checklist

Share and Join the Discussion