Trie Applications Overview — XOR, Autocomplete, Suffix

Trie Variant Summary

Binary Trie (XOR Maximization)

Insert numbers bit by bit from MSB. For max XOR: greedily pick opposite bit.

root = {}
def insert(n):
    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_with(x):
    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

Reverse Trie (Suffix Matching)

Insert reversed words. Query by reversing the suffix/pattern.

for word in words:
    node = root
    for c in reversed(word):
        node = node.setdefault(c, {})
    node['#'] = True

Counted Trie (Prefix Scores)

Track count at each node = number of words passing through.

node['count'] += 1  # on insert
return node['count']  # on prefix query

Offline Trie Processing

Sort queries, insert elements up to query bound, then answer.

sorted_queries = sorted(enumerate(queries), key=lambda x: x[1][1])
j = 0
for idx, (x, m) in sorted_queries:
    while j < len(nums) and nums[j] <= m:
        insert(nums[j]); j += 1
    answers[idx] = query(x)

When to Use a Trie

Scenario	Use Trie?
Multiple prefix queries	YES
Single prefix query	NO (simple loop)
Word search in grid with many words	YES
XOR maximization with bits	YES
Autocomplete / suggestions	YES
Suffix matching	YES (reverse trie)