Tries and string data structures

Computer Science and Engineering (B.E./B.Tech) · Data structures · free study notes for exams, placements and interviews

In short

A trie (prefix tree, also called a digital search tree) stores a set of strings as a tree of characters, where every path from the root spells a prefix, so lookup costs O(L) in the key length L and never depends on how many keys are stored. Around it sits a family of string structures - compressed/Patricia tries, suffix tries, suffix trees, suffix arrays with LCP, and the Aho-Corasick automaton - that answer prefix, substring and multi-pattern queries far faster than scanning. These appear in the Data Structures and Algorithms papers of almost every Indian university, carry marks in GATE CS/DA (complexity of trie operations, suffix arrays, KMP preprocessing), and are standard interview material at Amazon, Google, Microsoft, Flipkart, Zoho, Oracle, Samsung R&D, Arcesium and the DE Shaw/Goldman style quant-dev rounds. On the job they power search autosuggest, spell check, IP routing tables, AML name screening and Indic text input.

Explained

The trie: structure and operations

Definition: a rooted tree in which each edge is labelled with one character; a node represents the string formed by the edge labels from the root to it. The root represents the empty string.
Each node holds an array/map of children (size σ = alphabet) and a boolean isEnd marking that the path spells a complete key; counters (wordCount, prefixCount) are commonly added.
No node stores the full key. The key lives in the path, so common prefixes are stored once - "care" and "card" share four nodes.
Insert(word): walk from the root; for each character, follow the child if present, else create it; set isEnd at the last node. Time O(L).
Search(word): walk the characters; fail if a child is missing; succeed only if isEnd is true at the end. StartsWith(prefix) is the same walk without the isEnd check.
Delete(word): clear isEnd, then unwind - remove a node only if it has no children and is not the end of another word. Time O(L).
Traversal: a pre-order DFS collecting characters yields all keys in lexicographic order (if children are visited in alphabet order) - a trie is therefore a sorted dictionary, which a hash table is not.
Height = length of the longest key; number of nodes ≤ 1 + Σ|wᵢ|, with equality only when no two keys share a prefix.
Terminator convention: appending a sentinel $ (not in the alphabet) makes every key a leaf, which simplifies suffix structures and avoids the "prefix of another key" case.

Variants and space optimisations

Standard (uncompressed) trie: children as a fixed array of σ pointers - O(1) child lookup, but σ pointers wasted at every node. For σ = 26 and 8-byte pointers, 208 bytes per node.
Map/hash-children trie: HashMap<Character,Node> or sorted list - far less memory for sparse nodes, O(1) average or O(log σ) child lookup. Preferred for Unicode/Devanagari alphabets where σ is large.
Compressed trie (radix tree / Patricia trie): every chain of single-child nodes is merged into one edge labelled with a substring. A compressed trie over n keys has at most n leaves and so O(n) nodes, independent of key length. Used in routing tables and in Linux/PostgreSQL internals.
Binary (bitwise) trie: keys are the bits of integers, σ = 2, depth = word length (32 or 64). Used for maximum XOR pair/subarray, XOR with range constraints, and IP longest prefix match.
Ternary search tree (TST): each node holds one character and three children (lower, equal, higher). Space close to a BST, search O(L + log n), keeps sorted order - a good middle ground between trie and BST.
Double-array trie / succinct trie (LOUDS): production implementations that cut memory to a few bits per node; used in CJK/Indic input-method dictionaries.
Suffix automaton (DAWG) and the FM-index / Burrows-Wheeler transform are the compressed-index relatives; usually only named in a UG syllabus, examined in depth in electives.

Trie compared with hashing and balanced trees

Lookup: trie O(L) worst case; hash table O(L) to hash + O(1) average but O(n) worst case on collisions; balanced BST O(L log n) because each of the log n comparisons scans up to L characters.
A trie supports prefix queries, autocomplete, lexicographic listing, longest-prefix match and shared-prefix counting; a hash table supports none of these.
A trie's cost is memory and pointer-chasing (poor cache locality); a hash table is more compact and cache-friendly for pure exact lookup.
Tries never need rehashing or rebalancing, and there is no hash function and no collisions, so adversarial inputs cannot degrade them - one reason interviewers prefer tries for dictionary problems.

Single-pattern matching: KMP, Z-function and Rabin-Karp

Naive matching compares the pattern at every position: O(n·m) worst case (e.g. T = "aaaa…a", P = "aaab").
KMP failure function π[i] = length of the longest proper prefix of P[0..i] that is also a suffix of it. Built in O(m) by extending the previous value and falling back through π on mismatch.
KMP search: keep the matched length q; on mismatch set q ← π[q−1] instead of moving the text pointer back. The text index never decreases, so search is O(n); total O(n + m), O(m) extra space.
π also gives: shortest period of a string = n − π[n−1] (a string is periodic with that period iff n mod (n − π[n−1]) = 0), counts of prefix occurrences, and the shortest palindrome extension.
Z-function: Z[i] = length of the longest common prefix of S and S[i..]. Computed in O(n) with a sliding [l, r] window; matching is done on P + '#' + T, reporting every i with Z[i] = m. Equivalent in power to KMP and easier to code.
Rabin-Karp: hash the pattern and each window of the text with a rolling (polynomial) hash, compare hashes, and verify on a hit. Expected O(n + m), worst case O(n·m) if all hashes collide. Natural for multiple patterns of the same length and for 2-D matching.
Use a large prime modulus (e.g. 1e9+7 or a 61-bit prime) and a random base; fixed base 31 with mod 2⁶⁴ is attackable by anti-hash tests.
Boyer-Moore / Boyer-Moore-Horspool skip forward using bad-character and good-suffix rules - sub-linear in practice (grep uses this family), worst case O(n·m) for Horspool.

Aho-Corasick: a trie that matches many patterns at once

Build a trie of all k patterns (the goto function).
BFS the trie computing failure links: fail(v) = the deepest node whose string is a proper suffix of v's string. For depth-1 nodes, fail = root.
Compute output links (dictionary-suffix links) so that a match of a shorter pattern ending at the same position is also reported.
Scan the text once, following goto, falling back along fail on mismatch, and emitting outputs at each node.
Complexity: build O(Σ|Pᵢ| · σ) time and O(Σ|Pᵢ| · σ) space for an automaton-style transition table; search O(n + z) where z is the number of occurrences - independent of the number of patterns.
This is the engine behind virus/IDS signature scanning (Snort), profanity and keyword filters, and AML/sanctions name screening in Indian banks.

Suffix structures: trie, tree, array and LCP

Suffix trie of S ($-terminated): a trie of all n+1 suffixes. Substring search is O(m), but it has O(n²) nodes - unusable beyond toy strings.
Suffix tree: the compressed suffix trie - exactly n+1 leaves, ≤ 2n+1 nodes, O(n) space with edge labels stored as (start, end) index pairs. Built in O(n) by Ukkonen's algorithm (McCreight and Weiner are the older O(n) constructions).
- Answers: substring search O(m); number of occurrences = leaves under the matched node; longest repeated substring = deepest internal node; longest common substring of two strings via a generalised suffix tree; longest palindromic substring with suffix-tree LCA.
- Limitation: large constant factor (15-20 bytes per character in practice) and fiddly to implement - rarely asked to be coded in an interview.
Suffix array (SA): the array of starting indices of all suffixes in lexicographic order. Space just n integers - the practical replacement for a suffix tree.
- Construction: naive sort O(n² log n); prefix doubling with sorting O(n log² n); doubling with radix sort O(n log n); SA-IS / DC3 in O(n).
- Pattern search: binary search over SA gives O(m log n), or O(m + log n) with LCP information.
LCP array: LCP[i] = longest common prefix of SA[i−1] and SA[i]. Built in O(n) by Kasai's algorithm using the rank array.
- Uses: number of distinct substrings; longest repeated substring = max LCP; k-th lexicographic substring; longest common substring (sort both strings together and take max LCP across the boundary); range-minimum over LCP gives the LCP of any two suffixes.

Key points

Trie - tree of characters where the path spells the key; insert/search/delete O(L), independent of n.
isEnd flag - distinguishes a stored key from a mere prefix; forgetting it makes "ca" match when only "cat" was inserted.
Node count ≤ 1 + Σ|wᵢ|; shared prefixes are the only saving, so tries win on dense dictionaries.
Lexicographic order - DFS of a trie in alphabet order lists keys sorted; hash tables cannot do this.
Compressed trie / Patricia - merge single-child chains; O(n) nodes for n keys regardless of key length.
Binary trie - bits as edges, depth 32/64; solves maximum XOR pair and longest-prefix-match routing.
Ternary search tree - one char and three children per node; trie-like search with BST-like memory.
KMP π array - longest proper prefix that is also a suffix; preprocessing O(m), search O(n), total O(n+m).
Shortest period = n − π[n−1], valid as a true period only if n is divisible by it.
Z-function - LCP of S with each of its suffixes; O(n); equivalent to KMP for matching.
Rabin-Karp - rolling polynomial hash, expected O(n+m); must verify a hash hit character by character.
Aho-Corasick - trie + failure links; O(n + z) search for any number of patterns at once.
Suffix trie is O(n²) nodes; suffix tree is O(n) - the compression is the whole point.
Ukkonen builds a suffix tree in O(n); Kasai builds the LCP array in O(n).
Distinct substrings = n(n+1)/2 − Σ LCP[i].
Longest repeated substring = maximum LCP value (deepest internal suffix-tree node).
Suffix array search = O(m log n) by binary search; space n integers versus ~20n bytes for a suffix tree.
Memory is the trie's weakness - σ-sized child arrays and poor cache locality; use maps, compression or a TST when σ is large (Unicode, Devanagari).

Formulas and examples

Trie operation cost: T(insert) = T(search) = T(delete) = O(L), L = key length; space O(Σ|wᵢ| · σ) with array children, O(Σ|wᵢ|) with map children
Trie node upper bound: N ≤ 1 + Σ|wᵢ|; compressed trie: N ≤ 2n − 1 for n keys
Child-array memory = N × σ × p bytes (p = pointer size, σ = alphabet size)
KMP: π[i] = max{k < i+1 : P[0..k−1] = P[i−k+1..i]}; total time O(n + m), space O(m)
Shortest period of S (length n) = n − π[n−1]
Polynomial hash: h(S) = (Σ_{i=0}^{m−1} S[i] · b^{m−1−i}) mod q
Rolling update: h' = ((h − S[i]·b^{m−1}) · b + S[i+m]) mod q
Aho-Corasick: build O(Σ|Pᵢ|·σ), search O(n + z), z = occurrences reported
Suffix array: construction O(n log n) (doubling + radix) or O(n) (SA-IS); search O(m log n)
Distinct substrings of S = n(n+1)/2 − Σ_{i=1}^{n−1} LCP[i]
Suffixes of a string of length n = n (n+1 with the sentinel $)

Example 1 - Trie size and memory. Insert {car, card, care, cat, dog}.

Nodes created: root, c, ca, car, card, care, cat, d, do, dog → 10 nodes (9 non-root).
Total characters stored = 3 + 4 + 4 + 3 + 3 = 17; the trie needs only 9 character nodes, so shared prefixes save 8 nodes.
Memory with 26-pointer arrays and 8-byte pointers: 10 × 26 × 8 = 2,080 bytes (plus flags). With HashMap children holding only the 9 real edges, roughly 9 entries × ~48 bytes ≈ 432 bytes - the reason sparse tries use maps.
search("car") → true (isEnd set). search("ca") → false (node exists, isEnd not set). startsWith("ca") → true.
delete("card"): clear isEnd at "card", node has no children → remove it; "car" is still a key, so stop. Only 1 node is freed.

Example 2 - KMP failure function and search. P = "ababaca" (m = 7).

i	0	1	2	3	4	5	6
P[i]	a	b	a	b	a	c	a
π[i]	0	0	1	2	3	0	1

π[5]: candidate k = 3, P[3]='b' ≠ 'c'; fall back k = π[2] = 1, P[1]='b' ≠ 'c'; fall back k = π[0] = 0, P[0]='a' ≠ 'c' → π[5] = 0.
Search in T = "abababacaba" (n = 11), tracking matched length q: i=0..4 give q = 1,2,3,4,5. At i=5, T[5]='b' but P[5]='c' → q ← π[4] = 3; now P[3]='b' matches → q = 4. i=6 → 5, i=7 ('c') → 6, i=8 ('a') → 7 = m, so a match starting at index 8 − 7 + 1 = 2, i.e. T[2..8] = "ababaca". Reset q ← π[6] = 1 and continue; i=9, i=10 give q = 2, 3. One occurrence, at index 2, and the text pointer never moved backwards.
Shortest period of P = 7 − π[6] = 6; 7 mod 6 ≠ 0, so "ababaca" is not periodic.

Example 3 - Suffix array, LCP and distinct substrings. S = "banana", n = 6.

Rank	SA[i]	Suffix	LCP[i]
0	5	a	-
1	3	ana	1
2	1	anana	3
3	0	banana	0
4	4	na	0
5	2	nana	2

Σ LCP = 1 + 3 + 0 + 0 + 2 = 6; n(n+1)/2 = 6 × 7 / 2 = 21 → distinct substrings = 21 − 6 = 15.
Check by hand: lengths 1-6 give 3 + 3 + 3 + 3 + 2 + 1 = 15. ✔
Longest repeated substring = max LCP = 3 → "ana" (occurs at indices 1 and 3).
Searching "nan": binary search over the 6 suffixes, O(3 × log 6) ≈ 8 character comparisons instead of scanning.

Example 4 - Rabin-Karp rolling hash. Map a→1 … z→26, base b = 31, modulus q = 101, window m = 3.

h("abc") = (1·31² + 2·31 + 3) mod 101 = (961 + 62 + 3) mod 101 = 1026 − 1010 = 16.
Text "zabc": h("zab") = (26·961 + 1·31 + 2) mod 101 = 25,019 mod 101 = 25,019 − 24,947 = 72.
Roll to "abc": b^{m−1} = 961 ≡ 52 (mod 101); remove 'z' → 26 × 52 = 1,352 ≡ 39; (72 − 39) = 33; × 31 = 1,023 ≡ 13; + 'c' = 3 → 16. Equal to h("abc") → candidate match, verified character by character. Each slide is O(1).

Example 5 - Binary trie for maximum XOR. A = {3, 10, 5, 25, 2, 8}, 5-bit keys.

Insert each number's bits from MSB: 3 = 00011, 10 = 01010, 5 = 00101, 25 = 11001, 2 = 00010, 8 = 01000.
For each x, walk the trie preferring the opposite bit at every level. For x = 5 (00101): want 1 → 25's branch; then 1 → 25; then 0 → 25; … path yields 25.
5 XOR 25 = 00101 XOR 11001 = 11100 = 28, the maximum pair (e.g. 2 XOR 25 = 27, 3 XOR 25 = 26, 10 XOR 25 = 19).
Cost: O(n × 32) build + O(n × 32) queries, versus O(n²) for all pairs - decisive at n = 10⁵.

class Node:
    __slots__ = ("ch", "end")
    def __init__(self): self.ch, self.end = {}, False

class Trie:
    def __init__(self): self.root = Node()
    def insert(self, w):
        cur = self.root
        for c in w:
            cur = cur.ch.setdefault(c, Node())
        cur.end = True                      # O(L)
    def _walk(self, w):
        cur = self.root
        for c in w:
            if c not in cur.ch: return None
            cur = cur.ch[c]
        return cur
    def search(self, w):      n = self._walk(w); return n is not None and n.end
    def starts_with(self, p): return self._walk(p) is not None

Structure	Build	Query	Space	Best for
Hash table	O(Σ\	wᵢ\	)	O(L) avg	Low	Exact lookup only
Balanced BST	O(nL log n)	O(L log n)	Low	Sorted keys, few prefix queries
Trie	O(Σ\	wᵢ\	)	O(L)	High (σ per node)	Prefix search, autocomplete
Compressed trie	O(Σ\	wᵢ\	)	O(L)	O(n) nodes	Routing, sparse long keys
Suffix tree	O(n)	O(m)	~20n bytes	Any-substring queries
Suffix array + LCP	O(n log n)	O(m log n)	~8n bytes	Same queries, far less memory
Aho-Corasick	O(Σ\	Pᵢ\	·σ)	O(n + z)	O(Σ\	Pᵢ\	·σ)	Thousands of patterns, one pass

Where it is used

E-commerce and travel search: autosuggest and "did you mean" on Flipkart, Myntra, Amazon.in, MakeMyTrip and the IRCTC station picker - prefix tries (or Elasticsearch/Lucene, which uses an FST, a minimised automaton cousin of the trie) for type-ahead; suffix/n-gram indexes for infix matches.
Networking: router forwarding tables do longest prefix match on IP addresses using compressed binary tries (LC-trie, Patricia); relevant to roles at Cisco, Juniper, Nokia, Tejas Networks, Sterlite and C-DOT.
Banking and compliance: Aho-Corasick screening of customer names against sanctions/PEP lists under RBI KYC-AML directions, UPI VPA prefix lookup, and fuzzy name matching in UIDAI/Aadhaar-style demographic de-duplication (trie plus edit-distance DP).
Text input and language tech: Indic keyboards and transliteration dictionaries (Bhashini, Google Indic, Swalekh) use double-array or succinct tries; spell checkers, T9-style prediction and OCR post-correction.
Security and systems: signature matching in IDS (Snort), antivirus scanners, URL/domain blocklists at ISPs, log-pattern mining; key-value stores and databases use radix trees for in-memory indexes.
Bioinformatics and plagiarism detection: suffix arrays and the BWT/FM-index for read alignment (BWA, Bowtie) at labs such as NCBS/IISc, and longest-common-substring based document similarity.

Interview questions

Q: Why is trie search O(L) and not O(L log n)? A: At each of the L levels the next character indexes a child directly (array) or via a hash (map), so the number of stored keys never enters the cost.
Q: Trie or hash table for an autocomplete feature? A: Trie - it returns all keys with a given prefix by one walk plus a subtree traversal, and lists them in sorted order; a hash table would have to scan every key.
Q: How do you delete a word from a trie safely? A: Clear its isEnd, then unwind from the leaf upwards, freeing a node only when it has no children and is not itself the end of another word.
Q: How much memory does a trie waste, and how do you fix it? A: A σ-pointer array per node is mostly empty; use hash/sorted-map children, a ternary search tree, or path compression (Patricia), which bounds the node count at O(n).
Q: What exactly does the KMP failure function store? A: π[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of it - the matched length to resume from after a mismatch, so the text pointer never retreats.
Q: Why is a suffix trie impractical while a suffix tree is fine? A: The suffix trie has O(n²) nodes because every suffix contributes its own chain; compressing single-child chains into substring-labelled edges leaves ≤ 2n+1 nodes.
Q: How do you count the distinct substrings of a string? A: Build the suffix array and LCP array; the answer is n(n+1)/2 − Σ LCP[i], since each LCP value counts prefixes already seen in the previous suffix.
Q: Rabin-Karp is expected O(n+m) - when does it degrade? A: When hashes collide often (adversarial input or a weak/small modulus), every window needs character-level verification, giving O(n·m).
Q: You must find which of 50,000 banned keywords appear in each incoming message. Approach? A: Aho-Corasick: one trie of all keywords with failure links, then a single O(n + z) pass per message - the cost is independent of the keyword count.
Q: How does a trie find the maximum XOR of two numbers in an array? A: Insert all numbers as fixed-length bit strings into a binary trie; for each number, greedily follow the opposite bit at each level, which maximises high-order bits first - O(32n) overall.
Q: Suffix tree or suffix array in production? A: Suffix array with LCP - the same queries at O(m log n) instead of O(m), but a few bytes per character instead of ~20, and much simpler to build and serialise.
Q: How would you check whether one string is a rotation of another? A: Equal lengths, then search B inside A+A with KMP or Z - O(n) time, no extra structure needed.

Common mistakes

Treating a reachable trie node as a stored key - without checking isEnd, "app" is reported present when only "apple" was inserted.
Quoting trie search as O(L log n) or as depending on n; equally, forgetting that O(L) hides a per-level hash/array lookup and poor cache behaviour.
Sizing children as 26 when the input has digits, spaces, uppercase or Devanagari characters - index-out-of-bounds in labs, or silent corruption from c - 'a' on non-lowercase input.
Deleting nodes greedily on delete, destroying other words that share the prefix; or never freeing anything, so memory grows without bound.
Confusing the suffix trie (O(n²) nodes) with the suffix tree (O(n)), or claiming a suffix array needs O(n log n) query time - it is O(n log n) to build, O(m log n) to query.
Using Rabin-Karp without verifying a hash match, or using base 31 with mod 2⁶⁴, which is defeated by anti-hash test cases.
Mis-defining π as "longest prefix that is also a suffix" without the word proper - that would always give the whole string, and the fallback loop would never terminate.