What is a Trie?

Data Structures·3 min read·code in python

A trie, or prefix tree, stores strings by their characters: every node is one character and every word is a path from the root. Because you walk one node per character, insert, search and "does any word start with this?" all cost O(L) for a word of length L, no matter how many words are stored.

The intuition: a word is a path

Think of a paper dictionary. You do not read every entry to find queue: you open at q, then u, then e. Each letter narrows the search, and the words that share a beginning sit together.

A trie is that dictionary as a tree. The root is the empty string. Each edge is a character. Walking from the root spells a prefix, and a node marked as the end of a word says a real word finishes there. Two words that start the same way walk the same nodes until they differ, so queue and query share que and split after it.

How a trie stores words

Each node holds two things: a map from the next character to a child node, and a flag for "a word ends here". Inserting a word means walking character by character, creating a child whenever one is missing, and setting the flag on the last node.

Searching is the same walk without creating anything: if a character has no child, the word is not there. The difference between search and starts with is only the last line. Search asks for the end-of-word flag; a prefix search does not care, because reaching the node is the answer.

What a trie gives you that a hash set does not

A hash set answers one question well: is this exact string present? It hashes the whole string, so it cannot tell you what else starts with que.

A trie keeps the structure of the prefix, so it answers a family of questions: every word with a given prefix (autocomplete), the longest prefix of a string that is a stored word (routing, word break), and the words in alphabetical order (walk the children in order). That is why search boxes, spell checkers and routers use tries.

The code

pythonA trie with insert, search and prefix search.

class TrieNode:
    def __init__(self):
        self.children = {}      # character -> TrieNode
        self.is_word = False    # a word ends at this node


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:                      # one step per character
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None                  # the path ends early
            node = node.children[ch]
        return node

    def search(self, word):                  # is the whole word stored?
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):           # does any word start with it?
        return self._walk(prefix) is not None

Run it in the browser IDE, free on the platform. Open the IDE

Complexity

Time	O(L) per insert, search or prefix check, for a word of length L.
Space	O(N x L) in the worst case for N words of length L, less when words share prefixes.

The count of stored words never enters the cost: a trie with ten words and one with ten million answer a five-character lookup in the same five steps.

When to use it

Autocomplete and search suggestions, where you need every word behind a prefix.
Checking many words against a dictionary, as in word break or a spell checker.
Longest-prefix matching, the way a router picks a route for an address.
Word games and puzzles (Boggle, crosswords) where you prune a path the moment no word can follow.

Watch out for

Memory: one node per character is much heavier than a hash set of the same words.
Exact lookups only: if you never ask about prefixes, a hash set is simpler and faster.
Large alphabets: a fixed array of 26 children per node wastes space for Unicode; use a map.
Sorted or range queries over whole strings: a balanced tree fits those better.

Trie: questions we get

What is the time complexity of a trie?

O(L) for insert, search and prefix search, where L is the length of the word. The number of words stored does not change it.

Trie or hash table?

A hash table wins for exact lookups: less memory, shorter code. A trie wins the moment you ask about prefixes, because it keeps the shared beginning of the words as structure.

How much memory does a trie use?

One node per character on every distinct path, plus the map inside each node. Shared prefixes are stored once, so a dictionary of related words is cheaper than it looks; unrelated words are not.

Which interview problems use a trie?

Implement Trie, word search II, word break, replace words, longest common prefix, and autocomplete-style design questions.

Related concepts

Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.

Talk to mentor