Data Structures · Lesson 13 of 16

Tries (Prefix Trees)

Build a trie (prefix tree) in Python for autocomplete, prefix search and word games, and learn its time and memory trade-offs versus hash sets.

  • Intermediate
  • 15 min read
  • 4 objectives

Before this lessonLesson 12: Heaps and Priority Queues

What you will learn

  • Explain how a trie stores strings by shared prefixes
  • Implement insert, search and starts_with
  • Build autocomplete with prefix counts
  • Weigh trie memory cost against hash sets

Your Progress

0 of 16 lessons 0%

  • Lessons0 / 16
  • Completed0
  • Est. time left~ 4 hours

Create a free account to keep your progress on every device.

Tip: pressing Next marks this lesson complete automatically.

Type "sta" into a search box and it suggests "stack", "stackcone", "stable". A hash set can tell you instantly whether "stack" is a word, but it cannot efficiently answer "which words start with sta?" without checking every word. A trie (pronounced "try", from retrieval), also called a prefix tree, is built for exactly this question.

The idea: one character per edge

A trie is a tree where each edge is labelled with a character. The path from the root to a node spells a prefix, and a node is marked as the end of a word if that prefix is a complete word. Words that share a prefix share the same path, so "car", "card" and "care" store "car" only once.

(root)
  |
  c
  |
  a
  |
  r*          * = end of a word
 / \
d*  e*

Words: car, card, care

The cost of looking up a word depends on its length L, not on how many words are stored. Searching a million-word dictionary for "care" takes 4 steps.

Building a trie

Each node holds a dictionary from character to child node plus an end-of-word flag. Insert walks the characters, creating nodes as needed.

class TrieNode:
    def __init__(self):
        self.children = {}
        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 _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

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

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

t = Trie()
for w in ["car", "card", "care", "cat", "dog"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.search("cars"))
print(t.starts_with("ca"), t.starts_with("do"), t.starts_with("z"))
Output
True False False
True True False

Autocomplete

To suggest completions, walk to the prefix node and then do a depth-first search below it, collecting every word you pass. Visiting children in sorted order returns suggestions alphabetically.

class TrieNode:
    def __init__(self):
        self.children = {}
        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 complete(self, prefix, limit=5):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        results = []
        def dfs(n, path):
            if len(results) == limit:
                return
            if n.is_word:
                results.append(path)
            for ch in sorted(n.children):
                dfs(n.children[ch], path + ch)
        dfs(node, prefix)
        return results

t = Trie()
for w in ["stack", "stackcone", "stable", "stage", "start", "state", "static", "sql"]:
    t.insert(w)
print(t.complete("sta"))
print(t.complete("stac"))
print(t.complete("x"))
Output
['stable', 'stack', 'stackcone', 'stage', 'start']
['stack', 'stackcone']
[]

Counting words by prefix

If each node also stores how many words pass through it, "how many words start with pre?" becomes an O(L) walk. Search engines use counts like this (often weighted by popularity) to rank suggestions.

class Node:
    def __init__(self):
        self.children, self.count, self.is_word = {}, 0, False

root = Node()
def insert(word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, Node())
        node.count += 1
    node.is_word = True

def count_prefix(prefix):
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return 0
    return node.count

for w in ["apple", "app", "apply", "apt", "bat"]:
    insert(w)
print(count_prefix("ap"), count_prefix("app"), count_prefix("b"), count_prefix("c"))
Output
4 3 1 0

Where tries are used

  • Autocomplete and search suggestions in editors, IDEs and search bars.
  • Spell checkers and word games (Boggle, Scrabble solvers): prune a search as soon as a prefix matches no word.
  • IP routing: routers find the longest matching prefix of an address using binary tries over bits.
  • Tokenizers: many LLM tokenizers match the longest known token at each position with a trie-like structure.

Memory: the catch

Every node is a separate object with its own dictionary, so a trie can use many times more memory than a plain set of strings, especially when words share few prefixes. Common remedies:

  • Use a fixed array of 26 child slots for lowercase-only data (fast, but wastes space on empty slots).
  • A radix tree (compressed trie) merges chains of single-child nodes into one edge labelled with a whole substring, like "ack" instead of a, c, k.
  • If you only need exact lookups, a hash set is simpler and smaller. If you need prefix queries on a static list, a sorted list plus binary search can also work.
import bisect

words = sorted(["stack", "stackcone", "stable", "stage", "sql", "state"])
def with_prefix(prefix):
    i = bisect.bisect_left(words, prefix)
    j = bisect.bisect_left(words, prefix + "\uffff")
    return words[i:j]
print(with_prefix("sta"))
Output
['stable', 'stack', 'stackcone', 'stage', 'state']

Complexity

Operation (L = word/prefix length, N = total chars stored, k = results)

                     Trie             Hash set          Sorted list + bisect
insert               O(L)             O(L) average      O(n) (shifting)
exact search         O(L)             O(L) average      O(L log n)
starts_with          O(L)             O(total) scan     O(L log n)
list k completions   O(L + nodes      O(total) scan     O(L log n + k)
                     visited)
memory               O(N) nodes,      O(N)              O(N), compact
                     high overhead

Recap

  • A trie stores strings along root-to-node paths, sharing common prefixes.
  • Insert, search and prefix checks cost O(L), independent of how many words are stored.
  • An end-of-word flag separates "is a word" from "is a prefix".
  • DFS below a prefix node gives autocomplete; per-node counts give prefix counts.
  • Tries trade memory for speed; radix trees compress them.
# Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 14GraphsVertices, edges, adjacency lists, BFS and DFS intuition.