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.

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.

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.

When To Use It

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