Trie

A trie stores strings by shared prefixes. Each path from the root follows characters in a string.

It is useful when many strings share prefixes or when prefix lookup is the main operation.

Core Idea

Instead of storing each word separately, a trie stores common prefix structure once. Moving from one node to a child consumes one character.

Nodes usually store child links and a marker that says whether a word ends there.

Class Contract

Trie() creates an empty prefix tree.

insert(word) expects a string and stores its characters as a path from the root. The end marker distinguishes a complete inserted word from a prefix that merely leads to longer words.

Python Example

class Trie:
    def __init__(self):
        self.root = {}
 
    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node["$"] = True

The "$" marker records the end of a complete word.

Search and Prefix Search

The same structure can answer full-word and prefix queries:

def starts_with(root, prefix):
    node = root
    for char in prefix:
        if char not in node:
            return False
        node = node[char]
    return True

For full-word search, also check that the end marker exists after consuming every character.

Step-by-Step Example

Inserting "cat" and "car" shares the prefix "ca":

c -> a -> t
       -> r

The shared prefix is stored once, then the words branch at the third character.

Complexity

Insert, full-word search, and prefix search are O(L) where L is the length of the word or prefix. The space depends on the total number of stored characters after shared prefixes are accounted for.

Common Confusions

A trie is not the same as a hash set of strings. A hash set can answer full-word membership, but a trie exposes prefix structure.

The end marker is necessary because one word can be a prefix of another word.

Another common mistake is treating every node as a complete word. Only nodes with an end marker represent complete inserted words.

When To Use It

Use a trie for prefix search, autocomplete, dictionary matching, word games, and problems where many strings share starting characters.

Do not use a trie if the problem only needs a small number of full-string membership checks. A set may be simpler.

The Main Point

A trie stores shared prefixes explicitly. It is useful when prefix structure matters more than simple whole-string membership.