Tries, also known as Prefix Trees, are a tree data structure that stores and searches strings efficiently by reusing shared prefixes.

Tries power familiar features like search-engine query suggestions and spell checkers. They are also a common topic in coding interviews, especially in problems that involve prefix-based search or efficient string lookups.

This chapter covers:

A trie is a tree-based data structure that stores strings so prefix lookups run in time proportional to the prefix length.

Instead of storing whole words as standalone entries, a trie breaks them down character by character and reuses common prefixes.

Start with the word "design". In a trie, we store it as a sequence of connected nodes, where each node represents a single character.

Following the path from the root to 'n' gives the word "design".

Now add another word: "desktop".

"design" and "desktop" both start with "des". Instead of creating a completely new branch, the trie reuses the prefix "des".

Next, insert the word "destination".

It also starts with "des", so we share that prefix again and branch after it:

To summarize:

In code, a trie is built from a small node type, the TrieNode.

To represent a trie in code, we first need to define the building block of the trie, the TrieNode.

Each node in a trie keeps track of two important things:

Going back to our earlier example with the words "design", "desktop", and "destination":

All major trie operations like insert, search, and prefix search only require us to walk through the characters of the word once. So the time complexity is O(k) where k is the length of the word.

Prefix-heavy problems benefit directly from this property: prefix queries cost O(k), where k is the prefix length.

Four operations cover almost every trie problem: insert, search, prefix search, and delete. The implementations below use the Java TrieNode from the previous section, where children is an array of size 26 indexed by c - 'a'.

Walk down the trie one character at a time. If the path does not exist yet, create the missing nodes along the way. At the end, mark the last node as a word boundary.

For the word desktop, the loop visits each character. If the trie already contains design, the nodes for d, e, and s already exist and are reused. New nodes are created for k, t, o, and p. The isWord flag on the final p node is set to true.

The time complexity is O(k) where k is the length of the word. The space complexity is O(k) in the worst case, when none of the prefix is shared with existing words.

Walk the same path the insert would have taken. If any character is missing along the way, the word is not in the trie. If the walk completes, check the isWord flag on the final node to distinguish a full word from a prefix.

The helper findNode returns the node reached by walking the prefix, or null if the path breaks. It is shared between search and startsWith.

Search runs in O(k) time and O(1) extra space.

Prefix search is the same as search, except we do not care whether the final node is a complete word. If we can walk the prefix without hitting a dead end, at least one word in the trie has that prefix.

This single operation is the reason tries exist. A hash map can answer "is this exact word stored?" but cannot answer "is any word starting with des stored?" without scanning every entry.

Deletion is the trickiest trie operation because we have to walk down to confirm the word exists, then walk back up cleaning up nodes that are no longer needed.

A node can be removed only if both conditions hold:

The recursive deletion below returns true to its parent when the parent should detach this node.

Walking through an example clarifies the behavior. Suppose the trie contains design, desktop, and destination. Deleting desktop:

After the delete, the trie still contains design and destination, sharing the prefix des.

The table below assumes k is the length of the word, N is the total number of words stored, and σ is the size of the alphabet (26 for lowercase English).

The total space the trie itself occupies is the more interesting figure:

Array-based children give O(1) lookup per character but pay σ pointers per node, most of which are null. Hash-map-based children save memory at the cost of slower per-character lookup. For lowercase English the array form is the standard choice. For Unicode or large alphabets the hash-map form is the standard choice.

The most common practical use of a trie is autocomplete: given a prefix, return every word that starts with it.

The implementation has two phases. First, walk down to the node at the end of the prefix using findNode. Then, do a depth-first traversal from that node, collecting every word found along the way.

Suppose the trie contains design, desktop, destination, delight, and dog. Calling autocomplete("des"):

The output is ["design", "desktop", "destination"]. The branches under delight and dog are never visited because they sit under different prefixes.

The time complexity is O(p + m × L), where p is the length of the prefix, m is the number of matching words, and L is the average length of those matches. The autocomplete is fast specifically because the trie has already grouped all words by their prefix.

Both structures support fast key lookup, but they specialize in different operations.

A useful way to think about the choice: if the problem involves prefixes or ordered word traversal, use a trie. If the problem only involves exact lookups, a hash map is simpler and uses less memory.