Trie Applications Overview — XOR, Autocomplete, Suffix, Counted

Problem Statement#

This is a meta-overview, not a single LeetCode problem. By the time you finish this guide you should be able to walk into any FAANG trie interview and immediately classify the question into one of five families:

1. Vanilla prefix trie — autocomplete, prefix count, search-as-you-type.
2. Binary trie — max XOR, min XOR, XOR with constraints.
3. Reverse trie — suffix matching, suffix dedup, "ends with" queries.
4. Counted / weighted trie — prefix scores, weighted sums, popularity ranking.
5. Offline / persistent trie — bounded XOR, range XOR, versioned dictionaries.

Knowing the variants — and the signal that picks each one — is what separates "I know what a trie is" from "I can solve any trie problem in 5 minutes."

Why This Problem Matters#

Every FAANG company asks at least one trie problem. Amazon, Google, Microsoft, Meta, and Bloomberg pull from a remarkably small set of patterns — and the meta-skill of recognising which pattern applies is what interviewers actually probe. A candidate who reaches for a trie when the cue is "many prefix queries" or "bit-by-bit greedy" demonstrates the systems-level thinking that earns senior offers.

This overview is also the cheat sheet for production. Autocomplete services at Google, search suggestions at Amazon, IP routing tables (LPM), DNS resolution, ad-blocking domain filters, and bioinformatics suffix matching all run on one of these five variants. The same template you write on a whiteboard is the template that ships.

The Core Insight#

Every trie variant rests on three knobs:

• Alphabet — letters (A-Z, a-z), digits (0-9), bits (0/1), arbitrary tokens. The algorithm is identical; only the branching factor changes.
• Augmentation per node — terminal flag (vanilla), count (counted), value sum (weighted), parent pointer (persistent), version stamp (offline).
• Direction of insertion — forward (prefix matching), reversed (suffix matching).

Pick the right combination and the problem solves itself.

Visual Dry Run — All Five Variants Side by Side#

1. Vanilla Prefix Trie#

Insert "cat", "car"
       root
        |-- c
            |-- a
                |-- t (END)
                |-- r (END)

Use cases: word search, prefix count, "starts with" queries.

2. Binary Trie (XOR)#

Insert 5 (101), 3 (011)
       root
        |-- 0
        |   |-- 1
        |       |-- 1 → 011 = 3
        |-- 1
            |-- 0
                |-- 1 → 101 = 5

Greedy max-XOR walk: at each bit, prefer the opposite of the query bit.

3. Reverse Trie (Suffix)#

Insert "time", "me" → reverse: "emit", "em"
       root
        |-- e
            |-- m (END "me")
                |-- i
                    |-- t (END "time")

"me" is detected as a suffix of "time" because its reverse is a prefix of "time"'s reverse.

4. Counted Trie (Prefix Scores)#

Insert "abc", "ab"
       root
        |-- a (cnt=2)
            |-- b (cnt=2)
                |-- c (cnt=1)

Score of any prefix = node.cnt. Used for autocomplete ranking and prefix sum queries.

5. Offline Trie (Bounded XOR)#

Sort queries by mi.
Sort nums.
For each query (x, mi):
   while nums[j] <= mi: insert nums[j] into binary trie
   answer = max_xor(x)

Each element inserted once across all queries — total O((n+q) log V).

Solution (Optimal) — Reusable Templates#

Python — Five Templates#

# 1. Vanilla prefix trie
class Trie:
    def __init__(self): self.root = {}
    def insert(self, w):
        node = self.root
        for ch in w:
            node = node.setdefault(ch, {})
        node["#"] = True
    def search(self, w):
        node = self.root
        for ch in w:
            if ch not in node: return False
            node = node[ch]
        return "#" in node
    def starts_with(self, p):
        node = self.root
        for ch in p:
            if ch not in node: return False
            node = node[ch]
        return True
 
# 2. Binary trie (XOR)
def insert_bits(root, n, bits=31):
    node = root
    for b in range(bits, -1, -1):
        bit = (n >> b) & 1
        if bit not in node: node[bit] = {}
        node = node[bit]
 
def max_xor(root, x, bits=31):
    if not root: return -1
    node = root; xr = 0
    for b in range(bits, -1, -1):
        bit = (x >> b) & 1
        want = 1 - bit
        if want in node:
            xr = (xr << 1) | 1
            node = node[want]
        else:
            xr <<= 1
            node = node[bit]
    return xr
 
# 3. Reverse trie (suffix)
def insert_reversed(root, w):
    node = root
    for ch in reversed(w):
        node = node.setdefault(ch, {})
    node["#"] = True
 
# 4. Counted trie (prefix scores)
class CountedTrie:
    def __init__(self): self.root = {"_cnt": 0}
    def insert(self, w):
        node = self.root
        for ch in w:
            if ch not in node: node[ch] = {"_cnt": 0}
            node = node[ch]
            node["_cnt"] += 1
    def prefix_count(self, p):
        node = self.root
        for ch in p:
            if ch not in node: return 0
            node = node[ch]
        return node["_cnt"]
 
# 5. Offline trie (bounded XOR)
def offline_max_xor(nums, queries):
    nums.sort()
    sorted_q = sorted(((i, x, m) for i, (x, m) in enumerate(queries)), key=lambda t: t[2])
    root = {}
    ans = [0] * len(queries)
    j = 0
    for orig_idx, x, m in sorted_q:
        while j < len(nums) and nums[j] <= m:
            insert_bits(root, nums[j])
            j += 1
        ans[orig_idx] = max_xor(root, x) if root else -1
    return ans

JavaScript — Same Templates#

// 1. Vanilla prefix trie
class Trie {
  constructor() { this.root = {}; }
  insert(w) {
    let node = this.root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node._end = true;
  }
  search(w) {
    let node = this.root;
    for (const ch of w) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return !!node._end;
  }
}
 
// 2. Binary trie
function insertBits(root, n, bits = 31) {
  let node = root;
  for (let b = bits; b >= 0; b--) {
    const bit = (n >> b) & 1;
    if (!node[bit]) node[bit] = {};
    node = node[bit];
  }
}
function maxXor(root, x, bits = 31) {
  let node = root, xr = 0;
  for (let b = bits; b >= 0; b--) {
    const bit = (x >> b) & 1, want = 1 - bit;
    if (node[want]) { xr = (xr << 1) | 1; node = node[want]; }
    else { xr <<= 1; node = node[bit]; }
  }
  return xr;
}

Complexity Cheat Sheet#

Common Mistakes#

1. Reaching for a trie when only one query is asked — linear scan is O(N times L) and equally fast for a single check; tries amortise over many queries.
2. Using a 26-array of children for non-letter alphabets — pick a hashmap when the alphabet is large or sparse (digits, Unicode, byte-pairs).
3. Forgetting the terminal marker — without an END flag, you cannot distinguish "starts with cat" from "is exactly cat."
4. Inserting bits LSB-first — XOR greedy walk requires MSB-first; LSB destroys the optimality.
5. Mixing forward and reverse insertion — pick one direction per trie; reverse trie is for suffix queries, forward for prefix.
6. Trying to filter by value range on a binary trie — without offline sweep or persistence, you cannot. Sort queries.

Interview Tips#

• Memorise the five-question classifier: "many prefix queries?", "bits and XOR?", "suffix matching?", "scores or sums?", "bounded by mi or kth?". Each answer maps to one variant.
• Always start with the vanilla template; augment as the problem demands.
• For binary trie problems, write BITS = 31 (or 30 for ≤ 10^9, 60 for ≤ 10^18) explicitly. Off-by-one on bit-width is a common bug.
• State the build vs query complexity separately — interviewers love that decomposition.
• Acknowledge the O(N times L) total memory; for very large dictionaries, mention compression (Patricia, DAWG).

Follow-up Questions#

• When is a hash set as good as a trie? When you only need exact-match lookup with no prefix queries.
• Trie vs ternary search tree (TST)? TST uses less memory for sparse alphabets at the cost of slightly slower lookup.
• Trie vs DAWG / suffix automaton? DAWGs are tries with shared suffixes — same time, less space for dictionaries with overlap.
• Persistent trie? Each insert creates O(L) new nodes, sharing the rest. Used for versioned dictionaries and offline range queries.
• Distributed trie? Shard by first character or first k characters; cross-shard queries route to multiple servers.

Key Takeaways#

• Every trie problem reduces to one of five variants: vanilla, binary, reverse, counted, or offline.
• Recognising which variant applies is the meta-skill interviewers probe.
• Augmentation per node (cnt, total, value, version) is what specialises the variant.
• Direction of insertion (forward vs reverse) flips prefix queries into suffix queries.
• Binary tries on bits unlock XOR maximisation and bit-bucketing problems.
• Offline sweep + binary trie is the universal pattern for bounded XOR queries.