Tries

What it is

A trie, or prefix tree, stores sequences by sharing their prefixes. Each edge represents one symbol; the path from the root to a node spells a prefix. A terminal marker records whether that prefix is also a complete stored sequence.

For example, car and cart share the path for car. That node is terminal and also has a child. A path's existence therefore does not imply that it represents a complete word.

Scanning every stored string for a prefix match can examine much of the collection. A trie follows only the requested prefix, taking time proportional to its length. It trades additional nodes and pointers for direct access to shared prefixes. Hash sets remain simpler for exact membership alone; tries are especially useful when queries involve prefixes.

The same structure works for integers represented as fixed-width bit sequences. A binary trie has at most two children per node and supports queries governed by the most significant differing bit.

How to recognize it

Look for these signals:

• Many strings must support repeated exact or prefix searches.
• A query asks for the longest stored word that is a prefix of another string.
• Strings need distinguishing prefixes, or no stored string may prefix another.
• Prefix groups need counts, ranked selection, or removal of occurrences.
• A string must be segmented into dictionary entries, possibly minimizing cost.
• Integer queries involve maximizing XOR or counting XOR results below a bound.
• The eligible collection changes through insertions, deletions, or a moving window.

A trie is less compelling when there are only a few searches, or when sorting and scanning adjacent strings already solves the task efficiently.

The core technique

1. Build paths and track terminal nodes

Use a dictionary of children for a sparse alphabet. Store terminal information separately from child links. This basic version treats words as a set:

class Node:
    def __init__(self):
        self.children = {}
        self.terminal = False


def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = Node()
        node = node.children[ch]
    node.terminal = True


def longest_stored_prefix(root, query):
    node = root
    best = 0 if root.terminal else None
    for length, ch in enumerate(query, 1):
        node = node.children.get(ch)
        if node is None:
            break
        if node.terminal:
            best = length
    return None if best is None else query[:best]

Exact lookup requires both reaching the final node and finding its terminal marker. Prefix existence requires only reaching the final node.

For longest stored prefix, remember the most recent terminal encountered. The deepest reachable node might represent only an incomplete word. A terminal root represents the empty string.

To validate a prefix-free collection, reject an insertion if a terminal node is encountered before consuming the new word. At the endpoint, reject an existing terminal or any children: these indicate a duplicate or an existing longer word. Check before committing changes, or roll back a rejected insertion.

2. Add counts for distinguishing prefixes and selection

Store two quantities when duplicates matter:

• end_count: occurrences ending exactly at this node.
• subtree_count: occurrences ending anywhere in this node's subtree, including itself.

Insertion increments subtree counts along the entire path, including the root, and increments the endpoint's terminal count. Deletion reverses those updates, but only after confirming that an occurrence exists.

For a shortest distinguishing prefix, follow a string until its node has subtree count one. That prefix belongs to only one stored occurrence. Identical duplicates cannot be distinguished by a prefix; a string that prefixes another may also lack a distinguishing prefix unless an end-of-string symbol is explicitly included.

For ranked lexicographic selection, first reach the requested prefix node. Count its terminal occurrences before its children, because a word precedes its extensions. Visit children in sorted symbol order, subtracting whole subtree counts until the desired rank falls inside one subtree. Continue until selecting a terminal occurrence. To consume that occurrence, decrement counts along its path.

3. Traverse a dictionary trie during segmentation

Use a trie to generate dictionary matches beginning at each string position without repeatedly constructing candidate substrings. Combine this traversal with dynamic programming.

For minimum-cost segmentation, let dp[i] be the minimum cost of segmenting the suffix starting at i. Set dp[n] = 0; process positions backward. Every terminal reached from position i supplies a transition to the suffix after that word.

def minimum_cost(text, root):
    n = len(text)
    dp = [float('inf')] * (n + 1)
    dp[n] = 0
    for i in range(n - 1, -1, -1):
        node = root
        for j in range(i, n):
            node = node.children.get(text[j])
            if node is None:
                break
            # Terminal nodes carry their word's cost.
            if node.terminal:
                dp[i] = min(dp[i], node.cost + dp[j + 1])
    return dp[0]

Boolean feasibility replaces costs with reachable states. To reconstruct an optimal segmentation, store the selected next position. If deterministic tie-breaking is required, compare candidates by total cost, then total piece count, then next cut position; suffix states must use the same policy. Exclude empty dictionary entries so transitions always advance.

4. Use counted binary tries for XOR queries

Represent nonnegative integers with the same width B, including leading zeros. Insert from the most significant bit downward, maintaining subtree occurrence counts.

For maximum XOR, at each level prefer the child opposite the query bit, provided its count is positive. Otherwise take the matching child. This greedy choice works because a higher XOR bit outweighs all lower bits combined.

For XOR rank, count stored values y satisfying (x ^ y) < limit:

def xor_less(root, x, limit, B):
    if limit <= 0:
        return 0
    if limit >= (1 << B):
        return root.count
    node, answer = root, 0
    for b in range(B - 1, -1, -1):
        if node is None:
            break
        xb = (x >> b) & 1
        if (limit >> b) & 1:
            same = node.children[xb]
            answer += same.count if same else 0
            node = node.children[xb ^ 1]
        else:
            node = node.children[xb]
    return answer

An inclusive XOR band [lo, hi] has count xor_less(hi + 1) - xor_less(lo). For earlier-value queries, query before insertion. For bounded windows, expire old occurrences before querying. Counts handle duplicate values; per-value queues can retain indices when the query must identify a matching occurrence.

Common mistakes

• Confusing a reachable prefix node with a terminal word.
• Replacing occurrence counts with booleans when duplicates are allowed.
• Following zero-count branches after deletion.
• Choosing inconsistent bit widths or ignoring signed-number semantics.
• Using a strict XOR threshold where an inclusive bound is required.
• Traversing dictionary children in arbitrary order for lexicographic selection.
• Applying greedy word selection to segmentation instead of dynamic programming.

Complexity

Let S be total inserted string length, L a query length, n the segmentation input length, and M the longest dictionary word.

• String-trie construction uses O(S) expected time and O(S) nodes with dictionary children.
• Insertion, deletion, membership, and prefix queries take O(L) expected time.
• Ranked selection additionally pays for ordered child traversal; fixed small alphabets make this bounded per level.
• Segmentation takes O(nM) worst-case time and O(n) DP space, plus the dictionary trie.
• Binary-trie updates, maximum-XOR queries, and rank queries take O(B) time. Storing m values uses at most O(mB) nodes.

Shared prefixes reduce actual node counts, but per-node dictionaries can still make tries memory-intensive.