A trie (prefix tree) stores strings letter by letter: every word is a path from the root, every edge is one letter, and words with a common prefix share the beginning of the path. Searching depends on the length of the string, not on the size of the dictionary, which is why tries stand behind autocomplete, spell checking and IP routing tables.

The trie of seven words: green nodes mark the end of a word
The trie of seven words: green nodes mark the end of a word

The problem: prefix queries

"Which words start with ca?" A set of words answers "is car here?" in O(L), but a prefix question needs a scan of all n words: O(n · L). A trie answers it by walking down the prefix and collecting what lies below.

The structure and basic operations

A node holds a dictionary children (letter to child node) and a flag end: a word ends here. The flag is needed because a prefix is not yet a word: ca is in the tree as part of car and cat, but it was never inserted.

python
class TrieNode:
    def __init__(self):
        self.children = {}          # letter -> TrieNode
        self.end = False            # a word ends here

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

trie = Trie()
for w in ["car", "care", "cart", "cat", "do", "dog", "dot"]:
    trie.insert(w)

print(trie.search("car"), trie.search("ca"))
print(trie.starts_with("ca"), trie.starts_with("cb"))
text
True False
True False