Tries (Prefix Trees) — Data Structures Course

What you'll learn

A trie (prefix tree) stores strings by their characters, one per edge. Words that share a prefix share a path — making prefix search and autocomplete blazing fast, independent of how many words you've stored.

By the end you'll be able to:

Explain how a trie indexes strings character by character
Insert and search in O(L) for a word of length L
Use a trie for prefix queries and autocomplete

The prefix-tree idea

Each node represents a prefix; each edge adds one character. To store a word, walk down (creating nodes as needed) and mark the final node as a complete word. The key win: cat and car share the ca path, so common prefixes are stored once. Lookups cost O(L) — the word's length — no matter how many words the trie holds.

Build & search

Watch cat, car, and dog get inserted — notice car reuse the ca prefix — then a search for car:

Building a trie, then searching

Trie insert & search

•

1/17An empty trie — just the root. Each edge is one character; a path from the root spells a prefix.

Blue = the current path · green ring = a node that completes a word.

In code

Language

trie.py

class TrieNode:
    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_word = False

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.is_word = True

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

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

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Uses & trade-offs

Operation	Time	Note
`insert / search`	O(L)	L = word length, independent of the number of words
`prefix query`	O(P)	P = prefix length — the trie's superpower
Space	O(total characters)	Can be large; each node holds up to alphabet-size links

Key idea

A hash set answers "is this exact word present?" in O(L) too — but it can't answer "which words start with ca?" A trie makes prefix queries natural, which is why it powers autocomplete, spell-checkers, and IP routing tables.

Recap & quick check

Key takeaways

A trie stores strings by characters, one per edge; nodes represent prefixes.
Words with a common prefix share a path, stored once.
Insert and search are O(L) in the word length, not the number of words.
A completed word is marked with an is-word flag on its final node.
Tries excel at prefix queries: autocomplete, spell-check, and routing.

Quick check

1. In a trie, what does each edge represent?

2. Searching for a word of length L in a trie is:

3. Why do 'cat' and 'car' share nodes?

4. What can a trie do that a hash set cannot?

Tries branch by character. The last tree scales to disk, holding many keys per node. Next up: Module 22 — B-Trees & B+ Trees.