Tries & String Data Structures

Imagine you have a dictionary of 100,000 words and you want to answer: 'Does the prefix "auto" appear in any word?' With a sorted array you binary-search in O(log n · m) time; with a hash table you can only check exact strings, not prefixes. The trie solves the prefix problem definitively.

A trie is a rooted tree where:

1. Each node represents a string (the concatenation of edge labels from root to that node).
2. Each edge is labelled by a single character from alphabet Σ.
3. A node has at most |Σ| children, one per possible next character.
4. Nodes may be marked as terminal (end-of-word) to distinguish stored strings from mere prefixes.

The key invariant: the string represented by a node is uniquely determined by its position in the tree, not by any data stored at the node. This is what gives O(m) lookup — you simply walk the tree, consuming one character per edge, and either fall off (string absent) or reach a terminal (string present).

Alphabet size matters. For ASCII text, each node needs up to 128 child pointers. For DNA (Σ = {A,C,G,T}), only 4. For Unicode, a flat array is wasteful — a hash map per node or a compressed representation is used instead. This is the first of many space-versus-speed trade-offs in this topic.

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # marks a complete stored word

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True   # any path continuing from here is valid

Time complexity for all core operations on a trie over n strings with maximum length m and alphabet Σ:

Crucially, none of these depend on n. Once the trie is built, no matter if it holds 1,000 or 1,000,000,000 strings, a lookup for a length-m string is exactly m steps. This is unmatched by any comparison-based structure.

Space complexity is the trie's Achilles heel. In the worst case — when no two stored strings share any prefix — a trie has O(n·m) nodes. For a set of strings each of length 20 from a 26-letter alphabet, each node potentially carries 26 child pointers, so memory can reach O(n·m·|Σ|). In practice, with a hash map for children, wasted pointer slots disappear, but the overhead per node (Python dict, C++ unordered_map) can still be 40–100 bytes.

The fundamental tension: Array-indexed children (fast, O(1) per level) waste space on sparse alphabets; hash-map children (compact) add a constant-factor slowdown and memory overhead per node. Radix trees (compact tries) address this head-on.

Look at a trie storing only {'slow', 'slower', 'slowly'}. The path s→l→o→w is a long chain with no branching — each node has exactly one child. This is wasteful: we are paying per-character overhead to represent structure that holds no information (there is only one way to go).

A radix tree (also called a compressed trie or, in the binary case, a Patricia trie) collapses every maximal chain of single-child nodes into a single edge labelled by a string (not a single character). After compression:

• The node for 'slow' has two children: edge 'er' → terminal, edge 'ly' → terminal.
• The tree has O(n) nodes regardless of string lengths, because every internal node has at least 2 children.

Why O(n) nodes? By a classic leaves-versus-internal-nodes counting argument: a tree where every internal node has ≥2 children and has n leaves has at most n−1 internal nodes, so O(n) total nodes.

Patricia tries (Donald Morrison, 1968) are the binary-alphabet version and are used in the Linux kernel's routing table. Each 'skip value' stored at a node tells you which bit to branch on next, skipping zero-information bits. This allows O(m) lookups with O(n) nodes even for bit strings.

Trade-offs: Radix trees are faster in practice than standard tries (better cache behaviour, fewer allocations) but edge-label storage and string comparison add bookkeeping complexity. Insertion requires potentially splitting an existing edge when the new string diverges partway through a label.

# Conceptual insert into a radix tree
# Each node stores: children dict (label->node), is_end bool

def longest_common_prefix(s, t):
    i = 0
    while i < len(s) and i < len(t) and s[i] == t[i]:
        i += 1
    return i  # length of shared prefix

def radix_insert(node, key):
    for label, child in node.children.items():
        lcp = longest_common_prefix(key, label)
        if lcp == 0:
            continue
        if lcp == len(label):           # full edge consumed
            radix_insert(child, key[lcp:])
            return
        # Partial match: split the edge at lcp
        mid = TrieNode()                # new internal node
        mid.children[label[lcp:]] = child  # old child re-attached
        node.children[key[:lcp]] = mid
        del node.children[label]
        if lcp == len(key):             # new key ends at split
            mid.is_end = True
        else:
            mid.children[key[lcp:]] = TrieNode(is_end=True)
        return
    # No matching edge: insert new leaf
    node.children[key] = TrieNode(is_end=True)

The most visible real-world application of tries is autocomplete: given a typed prefix, return the k most frequent completions. This is exactly what happens in every search bar, terminal shell, and IDE.

Basic autocomplete is a DFS/BFS from the prefix's terminal node, collecting all words in the subtree. With a plain trie this is O(output size), which is fine for small result sets but wasteful if the subtree has millions of words and you only want the top 5.

Ranked autocomplete extends each trie node with the maximum frequency (or score) of any word in its subtree. During search, you use a priority queue and branch-and-bound: push the root of the prefix subtree, then repeatedly pop the highest-score node, expand its children, and stop once you have collected k terminal nodes. This gives the top-k results in O(k log |Σ| + m) time — you never visit low-scoring subtrees.

Ternary Search Trees (TST) are a practical hybrid: each node stores one character and has three children — less-than, equal, greater-than. They combine trie-like prefix queries with BST-like space efficiency, using O(n) space while supporting O(log n + m) average-case lookup. TSTs are the classic solution when Σ is large (e.g., Unicode) and the trie's flat child array would waste too much memory.

In production, systems like Elasticsearch use an FST (Finite State Transducer) — a minimised DFA that maps strings to values — which is even more space-efficient than a radix tree while still supporting prefix and fuzzy queries. The Lucene FST can store millions of terms in tens of megabytes.

import heapq

def top_k_completions(root, prefix, k):
    # Step 1: walk to the prefix node
    node = root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]

    # Step 2: BFS collecting (word, freq) pairs
    # Each node stores .freq (max freq in subtree) and .word (if terminal)
    results = []
    # max-heap via negation
    heap = [(-node.max_freq, prefix, node)]
    while heap and len(results) < k:
        neg_score, path, cur = heapq.heappop(heap)
        if cur.is_end:
            results.append((path, -neg_score))
        for ch, child in cur.children.items():
            heapq.heappush(heap, (-child.max_freq, path + ch, child))
    return results

A trie can answer prefix queries in O(m). But what about substring queries — does the pattern P appear anywhere in text T? Naively this is O(|T|·|P|). The breakthrough insight of suffix trees (Weiner 1973, McCreight 1976, Ukkonen 1995) is stunning: build a compressed trie of all |T| suffixes of T. Then any occurrence of P in T corresponds to P being a prefix of some suffix — i.e., a path from the root in the suffix trie.

Definition. Given text T of length n (with a unique terminator $ appended), the suffix tree ST(T) is the radix tree of the n+1 suffixes: T[0..n], T[1..n], …, T[n..n] (= '$'). Each leaf is labelled with the starting index of its suffix. Internal nodes represent repeated substrings (the string spelled by the path to that node occurs more than once).

Query. To find all occurrences of pattern P: walk the tree matching P character by character. If you fall off an edge, P does not occur. If you reach a node or a point inside an edge after consuming all of P, every leaf in the subtree below that point is an occurrence. This costs O(|P| + occ) where occ is the number of matches — optimal.

Ukkonen's algorithm builds the suffix tree online in O(n) time using suffix links — shortcut pointers from each internal node v (representing string aX) to the node representing X. The suffix link allows the algorithm to move from one implicit suffix extension to the next in amortised O(1) time, avoiding redundant re-traversal.

Space: O(n) nodes (by the radix-tree argument), but with a nasty constant — suffix trees use roughly 20·n bytes in practice, making them impractical for texts larger than ~100 MB. This motivated suffix arrays.

# Ukkonen's algorithm is ~80 lines; here is the core data model
# and a brute-force O(n^2) construction for clarity.

class STNode:
    def __init__(self, start, end):
        self.start = start   # edge label = text[start:end]
        self.end = end
        self.children = {}   # first char of edge -> STNode
        self.suffix_link = None
        self.leaf_index = -1 # >= 0 means this is a leaf

def naive_suffix_tree(text):
    """O(n^2) construction for illustration."""
    text = text + '$'
    root = STNode(-1, -1)
    for i in range(len(text)):
        suffix = text[i:]
        node = root
        j = 0
        while j < len(suffix):
            ch = suffix[j]
            if ch not in node.children:
                leaf = STNode(i + j, len(text))
                leaf.leaf_index = i
                node.children[ch] = leaf
                break
            child = node.children[ch]
            edge_len = child.end - child.start
            lcp = 0
            while lcp < edge_len and j + lcp < len(suffix) and \
                  text[child.start + lcp] == suffix[j + lcp]:
                lcp += 1
            if lcp == edge_len:
                node = child
                j += lcp
            else:
                # split edge
                mid = STNode(child.start, child.start + lcp)
                child.start += lcp
                mid.children[text[child.start]] = child
                node.children[text[mid.start]] = mid
                leaf = STNode(i + j + lcp, len(text))
                leaf.leaf_index = i
                mid.children[suffix[j + lcp]] = leaf
                break
    return root

Suffix trees are conceptually beautiful but memory-hungry (~20n bytes). A suffix array encodes the same information in just 4n bytes (an array of integers), making it the workhorse of practical string processing.

Definition. The suffix array SA of string T[0..n−1] is the array of starting positions of T's suffixes sorted in lexicographic order. Formally: SA[i] = j means the i-th lexicographically smallest suffix starts at position j.

Example: T = 'banana$'

• Suffixes sorted: $, a$, ana$, anana$, banana$, na$, nana$
• SA = [6, 5, 3, 1, 0, 4, 2]

Pattern search on SA: binary search for P as a prefix of the sorted suffixes. Two binary searches (leftmost and rightmost boundary) find all occ occurrences in O(|P| log n + occ) time. With the LCP array (longest common prefix between adjacent SA entries), this improves to O(|P| + log n + occ).

Construction: The naive O(n² log n) sort is easy to implement. The DC3/Skew algorithm (Kärkkäinen & Sanders 2003) and SA-IS (Nong et al. 2009) build the suffix array in O(n) time using clever divide-and-conquer / induced sorting.

The LCP Array. SA alone gives lexicographic order; the LCP array LCP[i] = length of the longest common prefix of SA[i−1] and SA[i] turns it into a data structure. Together, SA + LCP can simulate suffix tree operations and answer queries like 'what is the longest repeated substring?' in O(n) time.

Practical status: SA-IS is the algorithm of choice in production — it is O(n) time, O(n) space, cache-friendly, and implemented in libdivsufsort, which powers many bioinformatics tools, ripgrep, and bzip2.

def build_suffix_array_naive(text: str) -> list[int]:
    """O(n^2 log n) — correct and readable."""
    n = len(text)
    suffixes = sorted(range(n), key=lambda i: text[i:])
    return suffixes

def search_suffix_array(text: str, SA: list[int], pattern: str):
    """Binary search for pattern in text via SA. O(|P| log n)."""
    n, m = len(text), len(pattern)

    def compare(i):  # text[SA[i]:SA[i]+m] vs pattern
        s = text[SA[i]: SA[i] + m]
        if s < pattern: return -1
        if s > pattern: return  1
        return 0

    # Find leftmost match
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if compare(mid) < 0: lo = mid + 1
        else:                hi = mid
    left = lo

    # Find rightmost match
    hi = n
    while lo < hi:
        mid = (lo + hi) // 2
        if compare(mid) > 0: hi = mid
        else:                lo = mid + 1
    right = lo

    return sorted(SA[left:right])  # all occurrence positions

There is an even more compact structure: the Suffix Automaton (SAM), also called the Directed Acyclic Word Graph (DAWG). It is the minimal DFA (Deterministic Finite Automaton) that accepts exactly the set of all substrings of T.

Why is this useful? Every substring of T corresponds to a path in the SAM from the initial state. The SAM has at most 2n−1 states and 3n−4 transitions, so it is linear in the text length. You can:

• Check if P is a substring of T in O(|P|) time.
• Count distinct substrings in O(n) time.
• Find the longest common substring of two strings in O(n₁+n₂) time.
• Do online construction of a suffix index as the text arrives.

Suffix links in the SAM connect each state to the state representing the longest proper suffix of the current state's representative string. These links form a tree (the suffix link tree or parent tree) that is structurally equivalent to the suffix tree — you can convert one to the other.

Construction is online (left-to-right) and runs in O(n) time using the sa_extend operation, which adds one character at a time while maintaining the minimal DFA property by cloning states as needed.

The SAM is the most powerful of these string structures and is the algorithm of choice in competitive programming for substring counting and longest-common-substring problems. It is taught in depth at Codeforces/CP curricula and in some advanced algorithms courses.

# Suffix Automaton construction (online, O(n))
# Each state: len (longest string), link (suffix link), trans (transitions)

class SAMState:
    def __init__(self):
        self.len = 0
        self.link = -1
        self.trans = {}   # char -> state index

def build_sam(s: str):
    sa = [SAMState()]  # state 0 = initial state
    sa[0].len = 0
    sa[0].link = -1
    last = 0

    for c in s:
        cur = len(sa)
        sa.append(SAMState())
        sa[cur].len = sa[last].len + 1
        p = last
        while p != -1 and c not in sa[p].trans:
            sa[p].trans[c] = cur
            p = sa[p].link
        if p == -1:
            sa[cur].link = 0
        else:
            q = sa[p].trans[c]
            if sa[p].len + 1 == sa[q].len:
                sa[cur].link = q
            else:  # clone q
                clone = len(sa)
                sa.append(SAMState())
                sa[clone].len = sa[p].len + 1
                sa[clone].link = sa[q].link
                sa[clone].trans = dict(sa[q].trans)
                while p != -1 and sa[p].trans.get(c) == q:
                    sa[p].trans[c] = clone
                    p = sa[p].link
                sa[q].link = clone
                sa[cur].link = clone
        last = cur
    return sa

The structures in this module power a surprising range of systems:

IP Longest-Prefix Match. IPv4 routing tables store rules like '192.168.0.0/16 → interface eth0'. When a packet arrives, the router must find the most specific (longest-prefix) matching rule. A binary Patricia trie over the 32-bit addresses solves this in O(32) = O(1) operations — constant time regardless of routing table size. The Linux kernel's FIB (Forwarding Information Base) uses exactly this.

Genome Assembly and Search. The human genome is ~3 billion base pairs. BLAST, BWA, and Bowtie all use suffix arrays (or FM-indexes built on top of suffix arrays with BWT) to align short reads to the reference genome. The Burrows-Wheeler Transform (BWT) combined with suffix arrays gives the FM-index, which can search for a pattern in O(|P|) time using only ~2 bits per character of compressed text — a 16x space saving over the raw suffix array.

Spell Checking and Fuzzy Search. Tries support edit-distance bounded search via DFA intersection: build a trie for the dictionary and a DFA for 'all strings within edit distance k of the query', then intersect them by simultaneous traversal. This is O(|Σ| · |query| · k) per DFA state, far better than checking all dictionary words.

Compiler Symbol Tables. Token scanning in compilers uses tries (or minimal DFAs) to recognise keywords; the trie structure lets the scanner simultaneously advance through multiple candidate keywords.

Full-Text Search Engines. Inverted indexes (Lucene, Elasticsearch) use FSTs (Finite State Transducers — a generalisation of tries that map strings to values) to store the term dictionary compactly. Prefix queries, fuzzy queries, and range queries on the dictionary are all O(|query|) on the FST.

The FM-index (Ferragina & Manzini, 2000) is the apex of the string-indexing hierarchy: it compresses the text and indexes it simultaneously, supporting O(|P|) pattern search in the compressed representation.

Step 1 — BWT. The Burrows-Wheeler Transform rearranges T into BWT(T) such that identical characters cluster together (enabling compression) while still encoding all suffix information. Conceptually: sort all rotations of T$ lexicographically; the BWT is the last column of this sorted matrix. The last column is highly compressible (runs of identical chars) and, remarkably, invertible — you can recover T from BWT(T) alone.

Step 2 — Suffix Array. The first column F of the rotation matrix is exactly the sorted suffixes' first characters — derivable from the suffix array SA.

Step 3 — LF Mapping. The key operation is LF(i): given position i in BWT, map it to the position in F of the same character's occurrence. LF is computable in O(1) using two precomputed arrays:

• C[c]: number of characters in T lexicographically smaller than c.
• Occ[c, i]: number of occurrences of c in BWT[0..i].

Backward Search. To find pattern P[0..m−1], maintain a range [lo, hi) of SA rows matching P[j..m−1]. For each character P[j] from right to left: lo = C[P[j]] + Occ[P[j], lo−1]; hi = C[P[j]] + Occ[P[j], hi−1]. After processing all characters, SA[lo..hi) gives all occurrence positions. This is O(m) with O(n) preprocessing — and the index uses O(n log n) bits but with careful sampling can approach the compressed text size.

def bwt(text: str) -> tuple[str, int]:
    """Burrows-Wheeler Transform. Returns (BWT string, index of original)."""
    n = len(text)  # text should end with '$'
    # All rotations sorted: conceptual O(n^2 log n)
    rotations = sorted(text[i:] + text[:i] for i in range(n))
    bwt_str = ''.join(r[-1] for r in rotations)
    original_idx = rotations.index(text)
    return bwt_str, original_idx

def ibwt(bwt_str: str, idx: int) -> str:
    """Inverse BWT: recover original text."""
    n = len(bwt_str)
    table = [''] * n
    for _ in range(n):
        table = sorted(bwt_str[i] + table[i] for i in range(n))
    return table[idx]

# Example
bwt_str, idx = bwt('banana$')
print(bwt_str)          # 'annb$aa'
print(ibwt(bwt_str, idx))  # 'banana$'