Trie

Pronunciation: TREE or TRY

Updated September 30, 20263 min read

In short

A trie is a tree-shaped data structure that stores strings character by character, so all words that share a prefix also share the same path from the root.

What is a trie?

A trie, also called a prefix tree, is a tree that stores a set of strings, such as words or keys, one character per level. The root represents the empty string, each edge adds one character, and a node is marked as the end of a word when the path to it spells a complete entry. Because words with the same beginning share a path, car, card, and care all reuse the nodes for c, a, and r.

To insert or look up a word of length m, you start at the root and follow one child link per character, so both operations take O(m) time no matter how many words the trie holds. Finding all words that start with a prefix is just as direct: walk down to the prefix's node in O(m), then collect every word below it. Each node typically stores its children in a small hash map or in a fixed array with one slot per possible character.

Think of the thumb tabs in a paper dictionary: you jump to the C section, then narrow down to words starting with ca, then car, with fewer options after each letter. Tries power autocomplete and search suggestions, spell checkers, and word games. Routers use a close relative to find the longest matching address prefix in their routing tables.

A trie is often compared with a hash table. A hash table also looks up a whole key in O(m) time on average, since it must hash every character, but it can't efficiently answer prefix questions such as which words start with pre, and it doesn't keep keys in sorted order. The trade-off is memory: a plain trie can use many nodes, so compressed variants such as radix trees merge chains of single-child nodes into one.

Key takeaways

A trie stores strings one character per level, and words with a common prefix share nodes.
Insert and lookup take O(m) time, where m is the length of the word, regardless of how many words are stored.
Finding all words with a prefix takes O(m) to reach the prefix, plus time proportional to the matches collected.
Tries are used for autocomplete, spell checking, and prefix matching in routing tables.
The main cost is memory, which compressed variants such as radix trees reduce.

Example

A minimal trie built from nested Python dictspython

def insert(node, word):
    for char in word:  # one step per character: O(m)
        node = node.setdefault(char, {})
    node["$"] = True   # "$" marks the end of a complete word

def has_prefix(node, prefix):
    for char in prefix:  # also O(m), however many words are stored
        if char not in node:
            return False
        node = node[char]
    return True
trie = {}
for word in ["car", "card", "care"]:
    insert(trie, word)  # all three words share the path c -> a -> r
print(has_prefix(trie, "car"), has_prefix(trie, "cat"))  # True False

Readers ask

Why is it called a trie?

The name comes from the middle of the word retrieval. Edward Fredkin, who coined it in 1960, pronounced it like tree, but many people now say try to avoid confusing it with tree.

When should I use a trie instead of a hash table?

Use a trie when you need prefix queries, such as autocomplete or finding every key that starts with some text, or when you want to list keys in sorted order. For plain exact-match lookups, a hash table is usually simpler and uses less memory.

What is the time complexity of a trie?

Inserting, deleting, or looking up a word takes O(m) time, where m is the word's length, independent of how many words are stored. Listing all words with a given prefix takes O(m) to reach the prefix plus time proportional to the size of the results.