Trie

Definition: A search tree (also called Prefix Tree) used for storing strings where nodes store characters and root-to-node paths represent key prefixes.

How It Works

The root represents the empty string. Each edge represents one character, and children represent possible next characters extending the current prefix. A node’s depth in the tree equals the length of the prefix it represents.

• Search and insertion take O(k) time, where k is the string length, independent of the total number of stored keys. Unlike a Hash Table or Binary Search Tree (BST), lookup cost doesn’t grow as the dataset grows, only as the query string grows.
• Nodes mark a boolean flag is_end_of_word to distinguish a valid, complete stored string from a node that only exists as an intermediate prefix of a longer word. Without this flag, there’s no way to tell “abc” was inserted versus the trie just happening to contain a path through a -> b -> c as a prefix of something else.
• Each node typically holds a fixed-size array or hash map of child pointers, one slot per possible next character: 26 for lowercase English letters, 256 for extended ASCII, or a hash map for full Unicode support.

struct TrieNode:
    children: array[26] of TrieNode (or null)
    is_end_of_word: bool

insert(word):
    node = root
    for ch in word:
        idx = ch - 'a'
        if node.children[idx] is null:
            node.children[idx] = new TrieNode()
        node = node.children[idx]
    node.is_end_of_word = true

An array-based node gives O(1) child lookup at the cost of allocating 26 slots per node regardless of how many are actually used; a hash-map-based node uses only as much memory as there are actual children, at the cost of hashing overhead per lookup. The array approach wins for small, dense alphabets like lowercase English; the hash-map approach wins for large or sparse alphabets like full Unicode.

• Prefix queries (“all words starting with ‘pre’”) are answered by walking to the prefix’s node in O(k) time, then traversing the subtree beneath it to enumerate matches, far cheaper than filtering every stored string individually.

Complexity Analysis

Operation	Time	Notes
Insert	O(k)	k = length of the string
Search (exact match)	O(k)	independent of number of stored keys
Prefix search	O(k + m)	m = number of matches to enumerate
Delete	O(k)	plus possible cleanup of now-unused nodes
Space	O(alphabet_size * total_nodes)	can be large for sparse alphabets

Why It Matters

• Extremely fast prefix lookups, autocomplete suggestions, and spell-checking engines, since a shared prefix across many words is stored only once instead of duplicated per string.
• IP routing tables use a variant, a binary trie over address bits, or a compressed Patricia/radix trie, to perform longest-prefix-match lookups efficiently, which is exactly how routers decide where to forward a packet based on CIDR blocks.
• T9 predictive text and search-engine query-suggestion systems are built directly on trie prefix traversal, walking a shared structure of previously typed or indexed queries rather than filtering a flat list on every keystroke.

Common Pitfalls

• High memory usage from storing numerous empty/unused child pointers per node; a naive 26-pointer array per node for sparse alphabets wastes significant space, mitigated via a Radix Tree (compressing chains of single-child nodes into one edge) or by switching to hash-map children instead of fixed arrays.
• Forgetting to check is_end_of_word and instead treating “the search reached a valid node” as “the search found a complete stored word”; this incorrectly returns matches for strings that are only prefixes of stored words, not stored words themselves.
• Case-sensitivity bugs: inserting "Apple" and searching "apple" fail to match unless keys are normalized to a consistent case before both insertion and lookup.
• Deleting a word without checking whether its nodes are shared by other stored words; naive deletion can accidentally remove nodes still needed by a different word that shares the same prefix path.
• Choosing a trie for a small, static keyset where a plain hash table would use less memory and be simpler to implement, since a trie’s real advantage (prefix operations, shared-prefix compression) only pays off with large, prefix-heavy datasets.

Comparison

	Trie	Hash Table	Binary Search Tree
Lookup	O(k), k = key length	O(1) average	O(log n) average
Prefix queries	O(k + m), native support	Not supported	Not supported
Memory for many short shared-prefix keys	Efficient (shared prefixes)	Each key stored fully	Each key stored fully
Ordered iteration	Yes, lexicographic via DFS	No	Yes
Lookup cost driver	Key length only	Dataset size (average)	Dataset size (log)
Best fit	Large prefix-heavy string sets	General-purpose key-value	Ordered, range-queryable data

Example

Search-bar autocomplete predicting queries as you type is the classic trie use case.

Insert "cat", "car", "cart":
root -> c -> a -> t (end)
             \-> r (end) -> t (end)

The shared prefix "ca" is stored once, not three times. Searching for all words starting with "ca" walks 2 hops to reach the shared node, then explores its subtree to return ["cat", "car", "cart"] in O(k + results) time instead of scanning every stored string and checking each for a matching prefix.

Deletion, Traced

Deleting "cat" from the trie above (which also contains "car" and "cart"):

trie before: root -> c -> a -> t (end, "cat")
                          \-> r (end, "car") -> t (end, "cart")

delete "cat":
step 1: walk to the 't' node under c->a, unset its is_end_of_word flag
step 2: check if that 't' node has any children -> no children -> safe to remove it
step 3: walk back up to 'a' -> still has another child ('r'), and is not itself end_of_word -> stop, keep 'a'

trie after: root -> c -> a -> r (end, "car") -> t (end, "cart")

"car" and "cart" remain fully intact, since deletion only removes nodes that are both childless and not marking the end of some other stored word, walking back up the path only as far as sharing allows.

Variants

• Compressed Trie / Radix Tree: collapses chains of single-child nodes into a single edge labeled with a substring instead of one character, dramatically reducing node count for sparse tries where long unbranching chains are common.
• Ternary Search Trie: each node has only three children (less-than, equal, greater-than) instead of a full alphabet-sized array, trading a bit of lookup speed for much lower memory use on large alphabets.
• Suffix Trie / Suffix Tree: built from every suffix of a string rather than a set of whole words, enabling fast substring search, longest repeated substring, and other whole-text-indexing queries.

FAQ

Is a trie a binary tree? No. A binary tree has at most 2 children per node; a trie’s branching factor equals the size of the alphabet being indexed, which is typically much larger than 2.

When does a trie lose to a plain hash table? When prefix operations aren’t needed at all, just exact-match lookup, a hash table is usually simpler and more memory-efficient, since it doesn’t pay the per-character node overhead a trie incurs for every stored string.

Real-World Systems

• DNS resolution conceptually walks a domain name as a reversed prefix path (com -> example -> www), similar in spirit to how a trie decomposes a string into successive prefix hops.
• IP routing tables use binary tries over address bits (or compressed Patricia tries) to perform longest-prefix-match: given a destination IP, find the most specific matching CIDR block by walking as far down the bit-trie as the routing table has entries for.
• Autocomplete and spell-check in text editors and search engines store a large dictionary as a trie, so every keystroke narrows the search to a subtree rather than re-filtering the entire word list.

Common Interview Questions

• How would you implement startsWith(prefix) efficiently? — walk the trie one character per level; if every character is found, the prefix exists, in O(k) time regardless of dictionary size.
• Why not just use a hash set of all valid prefixes instead of a trie? — a hash set of prefixes duplicates storage for every prefix of every word (n words of length k need O(n*k) prefix entries), while a trie shares that storage automatically through its structure.
• How do you delete a word without breaking other words? — recursively delete from the leaf inward, but only physically remove a node if it has no other children and isn’t itself the end of a different word.

Related Terms

• Hash Table
• Binary Search Tree (BST)
• Recursion
• Big-O Notation
• IP Addressing and Subnetting