Introduction to Tries

A Trie (also known as a prefix tree or digital tree) is a tree-like data structure that stores a dynamic set of strings, commonly used for efficient prefix-based searching. Each node represents a character, and paths from the root to a node represent prefixes. Nodes often mark the end of a complete word. Tries are fundamental in applications like autocomplete, spell checkers, and IP routing.

Trie Variants and Interview Patterns

1. Autocomplete with Frequency (Top-K Suggestions)

This variant augments the basic Trie to support prefix-based autocomplete by tracking how often words appear and caching the most frequent completions. Each node can carry metadata like frequency counts or a list of popular suffixes.

Modified Template: Extend TrieNode with frequency and suggestions (list of top-k frequent words for the prefix up to that node). Insertion updates these fields. To get suggestions for a prefix, traverse to the prefix node and return its stored list.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False
        self.frequency = 0           # new: count occurrences of word ending here
        self.suggestions = []        # new: top-k frequent words with this prefix

Example Problem – LeetCode 642: Design Search Autocomplete System. Given sentence history with frequencies, return top 3 frequent sentences for a prefix. E.g., history: "i love you" (5), "island" (3), "ironman" (2), "i love leetcode" (2). User types "i", suggest ["i love you", "island", "i love leetcode"].

Code (Key Parts - Insertion Logic):

# Assume K and freq_map (word -> overall_frequency) are defined
def insert_word_with_suggestions(root, word, freq_map, K):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
        
        # Update suggestions at this prefix node
        # Add current word to consideration for suggestions
        temp_suggestions = list(node.suggestions) # copy current
        if word not in [s_word for s_word, s_freq in temp_suggestions]: # Avoid adding if already there
             # We need the actual frequency of the word being inserted for sorting
             current_word_freq = freq_map.get(word, 0) # Get actual frequency
             temp_suggestions.append((word, current_word_freq))

        # Sort by frequency (desc) then alphabetically (asc) for tie-breaking
        temp_suggestions.sort(key=lambda x: (-x[1], x[0]))
        node.suggestions = temp_suggestions[:K] # Keep top K

    node.end_of_word = True
    node.frequency = freq_map.get(word, 0) # Set frequency of the word itself

2. Word Search II (Trie + Backtracking on Board)

This pattern integrates a Trie with backtracking DFS on a grid to find dictionary words. The Trie acts as a prefix filter for the DFS.

Modified Template: Trie nodes store the complete word at the end node. Once a word is found, it can be marked as collected (e.g., node.word = None).

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None    # store full word when this node marks end of a word

Example Problem – LeetCode 212: Word Search II. Given an m x n board and a list of words, find all words on the board. Words are formed from adjacent letters (horizontally/vertically, no cell reuse per word).

Example Board:

Words: ["oath","pea","eat","rain"]. Output: ["oath","eat"].

Approach: Build Trie of words. For each cell, start DFS. If current prefix not in Trie, prune. If node has .word, add to results. Mark visited cells, backtrack.

Code (Backtracking Integration - DFS):

def dfs_word_search(board, i, j, node, result_set): # result_set to store found words
    ch = board[i][j]
    if ch == '#' or ch not in node.children: # Visited or no prefix
        return

    node = node.children[ch]
    if node.word:  # Found a word
        result_set.add(node.word)
        node.word = None  # Avoid duplicate finds for the same word instance

    board[i][j] = '#'  # Mark visited
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    for dr, dc in directions:
        nr, nc = i + dr, j + dc
        if 0 <= nr < len(board) and 0 <= nc < len(board[0]):
            dfs_word_search(board, nr, nc, node, result_set)
    board[i][j] = ch  # Unmark (backtrack)

3. Longest Prefix Matching

Use a Trie to find the longest prefix of a query string that exists as a word in a dictionary. Useful in IP routing or autocomplete for the longest valid prefix.

Modified Template: Standard Trie. The search logic differs: traverse Trie with query characters, track the deepest node that marked end_of_word.

def longest_prefix_of(root, query_string):
    node = root
    longest_found_prefix = ""
    current_prefix_path = ""
    for char_in_query in query_string:
        if char_in_query not in node.children:
            break  # No further match
        node = node.children[char_in_query]
        current_prefix_path += char_in_query
        if node.end_of_word: 
            longest_found_prefix = current_prefix_path # Update if current path is a word
    return longest_found_prefix

Example Problem – GeeksforGeeks: Longest Prefix Matching. Dictionary: {are, area, base, cat, cater, children}. Query "caterer" -> "cater". Query "basemexy" -> "base". Query "child" -> "" (if "child" itself isn't a word).

Code (Longest Prefix Function):

# Assuming 'trie' is an instance of a Trie class with a 'root' attribute
def get_longest_prefix_match(trie_root, query):
    node = trie_root
    longest_match = ""
    current_match = ""
    for char in query:
        if char not in node.children:
            break
        node = node.children[char]
        current_match += char
        if node.end_of_word:  # Check if this prefix is a complete word in trie
            longest_match = current_match
    return longest_match

4. Word Dictionary with Wildcards (Regex-Like Search)

Modifies Trie to support search queries with wildcards (e.g., . matching any letter). The Trie nodes are standard; the search algorithm changes.

Modified Template: Search uses DFS/backtracking. If char is ., try all children nodes recursively. If not ., follow the specific child. Succeeds if path ends on an end_of_word node.

Example Problem – LeetCode 211: Add and Search Word. Design addWord(word) and search(pattern). After adding "bad", "dad", "mad": search("pad") -> False, search("bad") -> True, search(".ad") -> True, search("b..") -> True.

Code (Wildcard Search - part of a Trie class):

# Inside a Trie class with self.root
def search_with_wildcard(self, word: str) -> bool:
    def dfs(node, index):
        if index == len(word):
            return node.end_of_word
        
        char = word[index]
        if char == '.':
            for child_node in node.children.values():
                if dfs(child_node, index + 1):
                    return True
            return False
        else:
            if char not in node.children:
                return False
            return dfs(node.children[char], index + 1)
            
    return dfs(self.root, 0)

Interactive Trie Animations