Tries — Master Recap & Cheatsheet

Tries Master Cheatsheet

Core Operations Complexity

Operation	Time	Space
Insert word	O(L)	O(L * 26) array, O(L) hashmap
Search word	O(L)	O(1)
Prefix check	O(L)	O(1)
Word Search II	O(MN3^L) pruned	O(sum lens)
Max XOR pair	O(32*n)	O(32*n)

Standard Trie Template

class TrieNode:
    def __init__(self):
        self.children = {}  # or [None]*26
        self.is_end = False
        # Optional extras:
        # self.count = 0      # words through this node
        # self.word = ""      # word ending here (for Word Search II)

Binary Trie (XOR) Template

def insert(n, root):
    node = root
    for bit in range(31, -1, -1):
        b = (n >> bit) & 1
        if b not in node: node[b] = {}
        node = node[b]

def max_xor_query(x, root):
    node = root; xr = 0
    for bit in range(31, -1, -1):
        b = (x >> bit) & 1; want = 1 - b
        if want in node: xr = (xr << 1) | 1; node = node[want]
        else: xr <<= 1; node = node[b]
    return xr

Decision Guide

Need prefix search?          → Trie (vs HashSet)
Multiple words in grid?      → Trie + Grid DFS (Word Search II)
Autocomplete?                → Trie + sorted lists at each node
Max/Min XOR?                 → Binary Trie (bit by bit)
Suffix matching?             → Reversed Trie
Words counted by prefix?     → Trie with count field
Combined prefix + suffix?    → Concatenate suf#pref as key

Problem Index

#	Problem	Key Trick
01	Implement Trie	Basic insert/search/prefix
02	Design Add Search Words	Wildcard DFS with '.'
03	Word Search II	Trie pruning in grid DFS
04	Replace Words	First '#' found = root
05	Maximum XOR Two Numbers	Binary trie greedy
06	Search Suggestions	Sort + bisect or trie lists
07	Longest Word in Dictionary	Only traverse is_end nodes
08	Palindrome Pairs	HashMap prefix/suffix check
09	Stream of Characters	Reverse trie + active nodes
10	Prefix and Suffix Search	suf#pref concatenated key
11	Sum of Prefix Scores	count at each trie node
12	Concatenated Words	Word break DP + word_set
16	Max XOR with Element	Offline sort + binary trie