Low Level Design: Trie Data Structure – Tech Interview Dot Org

Trie Node Structure

Each node in a trie holds a fixed-size array of 26 child pointers (one per lowercase letter) or a hashmap for tries supporting arbitrary character sets. A boolean flag is_end_of_word marks whether the path from root to this node forms a complete key. For key-value tries, the node also stores an optional value. The root node represents the empty prefix; a node at depth d represents a unique prefix of length d. Using a fixed array gives O(1) child lookup but wastes memory when most slots are null; a hashmap trades some lookup speed for a smaller footprint.

Insert Operation

To insert a key of length L: start at the root and walk character by character. At each step, compute the child index (character – ‘a’ for lowercase ASCII). If the child pointer is null, allocate a new node and attach it. After processing every character, set is_end_of_word = true on the final node. Time complexity is O(L); space complexity is O(L) in the worst case when no prefix is shared with existing keys. Because allocation only happens for missing nodes, inserting a key that is a prefix of an existing key requires no new nodes at all.

Search Operation

Exact search traverses the trie character by character. If any child pointer is missing, return false immediately. After consuming all characters, return the value of is_end_of_word. This correctly distinguishes "app" (a stored key) from "ap" (only a prefix). Time is O(L). Prefix search is identical but skips the final is_end_of_word check — it returns true if the traversal completes without hitting a null pointer, confirming the prefix exists. Both operations never backtrack, making tries faster than balanced BSTs for string lookups when keys share prefixes.

Prefix Enumeration and Autocomplete

To enumerate all keys with a given prefix, first traverse to the node representing that prefix (O(P) where P = prefix length). From that node, run a DFS collecting characters along each path; whenever is_end_of_word is true, emit the accumulated string. For top-K autocomplete with scoring, store a score or frequency counter at each terminal node. During DFS, maintain a min-heap of size K; prune branches where the max possible score in the subtree cannot beat the heap minimum. Precomputing the maximum score in each subtree (stored on every node) enables this pruning. This approach powers autocomplete in search engines where millions of prefixes are queried per second against a trie built from query logs.

Memory Optimization

A children array of 26 pointers consumes 26 × 8 = 208 bytes per node on a 64-bit system, most of it wasted when children are sparse. Alternatives:

Hashmap of children: allocates only used slots; lower memory but pointer-chasing overhead.
Sorted compact array: store only (character, pointer) pairs for existing children; binary search within the node for O(log k) lookup where k is local branching factor.
Double-array trie (base/check arrays): encodes the entire trie into two integer arrays; very cache-friendly and space-efficient but complex to implement and update.
DAWG (Directed Acyclic Word Graph): minimized trie that merges identical suffixes across keys. A DAWG for a dictionary of 100K English words can be an order of magnitude smaller than the equivalent trie because common suffixes like "-ing" and "-tion" are stored once.

Compressed Trie (Patricia Tree / Radix Tree)

In a standard trie, chains of single-child nodes are common — for example inserting only "interview" creates nine nodes, one per character. A compressed trie (Patricia tree or radix tree) collapses these chains: each edge carries a string label rather than a single character. Node count drops from O(total characters across all keys) to O(number of keys). When inserting a new key that diverges mid-edge, split the edge at the divergence point: create a new internal node, attach the remainder of the old edge label and the new key’s suffix as two children. This makes tries practical for large IP routing tables and file-system path stores where key counts are modest but key lengths are large.

IP Routing with Longest Prefix Match

IP routing requires finding the most specific (longest) prefix that matches a destination address. A binary trie keyed on IP address bits solves this: walk the trie bit by bit, recording the last node where a route was stored. After consuming all 32 bits (IPv4) or 128 bits (IPv6), return the last recorded route. Hardware implementations use TCAM (Ternary Content-Addressable Memory) for O(1) lookup at line rate, but TCAM is expensive and power-hungry. Software routers use compressed tries organized into 2-4 stride levels (e.g., /8, /16, /24, /32 for IPv4) stored in arrays for cache efficiency. The Linux kernel’s FIB trie uses a "LC-trie" (level-compressed trie) with variable stride to minimize memory accesses per lookup.

Suffix Trie and Suffix Array

A suffix trie is built by inserting all N suffixes of a string of length N. It enables O(L) substring search: any occurrence of pattern P is found by traversing P from the root. The drawback is O(N^2) space in the worst case. A suffix tree (compressed suffix trie) reduces this to O(N) nodes. For space-critical applications, a suffix array stores only the starting indices of all suffixes in sorted order — O(N) integers. Pattern matching on a suffix array uses binary search: O(L log N) with naive comparison or O(L + log N) with LCP (longest common prefix) arrays. Suffix arrays are used in bioinformatics for genome alignment (BWA, Bowtie) and in full-text search engines. Constructing a suffix array in O(N) time is possible via the SA-IS algorithm.

What is the time complexity of trie operations?

Insert, search, and delete in a trie are O(L) where L is the length of the key. This is independent of the number of stored keys, making tries faster than hash maps for prefix-based operations. The tradeoff is space: each node may hold up to 26 (or alphabet size) child pointers, making tries memory-intensive for sparse key sets.

How does a Patricia trie differ from a standard trie?

A Patricia trie (compact trie, radix tree) compresses single-child chains into single edges labeled with substrings rather than individual characters. This reduces space significantly for sparse tries where most keys share long common prefixes. Patricia tries store the number of bits to skip at each node. Linux uses a Patricia trie for IP routing table lookups.

How is a trie used for autocomplete?

A trie stores all indexed strings. At each node, insert DFS terminates nodes that mark complete words. For autocomplete, traverse to the node matching the prefix, then enumerate all words in the subtree below that node. To return the top-N results by popularity, augment each node with a score and prune DFS branches whose best possible score is below the N-th best found so far.

What is a suffix array and how does it relate to tries?

A suffix array stores all suffixes of a string sorted lexicographically, enabling O(L log N) substring search. It is more space-efficient than a suffix trie (which stores all suffixes explicitly). Suffix arrays are used in bioinformatics (genome sequence search), search engines (full-text substring indexing), and data compression (BWT transform). The DC3 algorithm builds a suffix array in O(N).

How is a trie used for IP routing (longest prefix match)?

IP routing tables store CIDR prefixes. A binary trie represents the 32-bit IP address bit by bit. Each leaf is a routing entry. Longest prefix match traverses the trie bit by bit, keeping track of the last matched prefix. For IPv4, the trie has depth 32. Hardware routers use TCAM (ternary content-addressable memory) for O(1) LPM, while software routers use Patricia tries.