Skip to content

Tries

Lesson 5 of 7 in Recursion, Trees & Graphs · 30 min · Advanced

A tree of letters where shared prefixes share a path.

Introduction

Your phone's keyboard suggests "cardigan" the moment you type "car". How can it find every word that starts with "car" without scanning the whole dictionary?

A dictionary can hold hundreds of thousands of words. Testing each one to see if it starts with "car" would be a long scan, and it would start over with every letter you type. A hash map doesn't help much either: it can tell you whether "car" is a word, but it files "car", "card" and "cardigan" in unrelated buckets.

So give each word a route instead. The first letter picks one road, the second letter picks the next, and so on. Where would the words that start with "car" be?

Lesson overview

This lesson will show you how to:

  • Explain why a trie finds prefix matches in time proportional to the prefix length.
  • Trace how inserting words creates shared paths and end-of-word markers.
  • Implement insert and search on a trie, using one child slot per letter.
  • Spot when a hash set beats a trie for exact-word lookups.
  • Compare the memory cost of a trie with the raw text it stores.

The picture

•root: no letters yetshared by cat, car, cardring: a word ends hereTrie with 9 nodes. Words stored: car, card, cat, dog.

Mental model

Picture a hiking trail with a signpost at every fork. Each sign shows a few letters, and to reach "cat" you take the c road, then the a road, then the t road. Words that begin the same way walk the same road for a while before it splits, and a small ring on a post means "a word ends right here".

A trie is a tree of letters: each word is a path from the root, and words that start the same share the same first stretch of path.

Words to know

trie
A tree that stores words, one letter per edge. The path from the root to a node spells a prefix. Said "try", from the word retrieval.
prefix
The first few letters of a word: "c", "ca" and "car" are all prefixes of "card". Every node in a trie stands for one prefix.
edge (character)
The link from a node to one of its children. The letter lives on the edge, as the key in the parent's children map, not inside the node.
end-of-word marker
A flag on a node (drawn as a double ring) that says the path to here is a stored word, not just the start of one. "car" and "card" both carry one.
children map
How a node keeps its children: a map from letter to child node. It only holds the letters that actually occur, and it works for any alphabet.
array of 26
A faster, fixed alternative for lowercase a to z: slot 0 is a, slot 25 is z. Lookup is a single index, but every node pays for 26 slots, even when it has one child.
autocomplete
Finding the prefix's node, then listing every stored word below it. Reaching the node costs one step per letter; listing costs one visit per node below it.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The problem asks "does any stored word start with this?", or wants every word that does.
  • Yes: Autocomplete, type-ahead, search suggestions or a dictionary that is searched letter by letter.
  • Yes: Many words share beginnings, and you query by prefix about as often as by whole word.
  • Yes: A pattern such as "b.d" has to match many words, or you walk a board and a word list together.

Not this when

  • No: You only ask "is this exact word stored?". A hash set answers in one step and uses far less memory.
  • No: You have only a handful of words, or one long text to search inside. Building a trie costs more than it saves.
  • No: The words share almost nothing and memory is tight. Every node carries a children container, so a trie can be much bigger than the raw text.

Which pattern fits?

  1. Which pattern? 1 of 5

    As the user types, show every stored word that starts with the letters typed so far.

  2. Which pattern? 2 of 5

    A list of 10,000 words is fixed. Many queries each ask whether one exact word is in the list.

  3. Which pattern? 3 of 5

    Words are given in sorted order. Find the first word that starts with a given prefix, using almost no extra memory.

  4. Which pattern? 4 of 5

    Words are added over time. A query like "b.d" must match "bad" and "bid", where the dot stands for any one letter.

  5. Which pattern? 5 of 5

    Each person in a family tree has any number of children. Find how many generations the tree has.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. root = an empty node
  2. for each word in words:
  3. 1node = root
  4. for each letter ch in word:
  5. 2if node has no edge for ch:
  6. 3give node a new child for ch
  7. 4node = the child for ch
  8. 5mark node as the end of a word
  9. 6return root

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
    return root
Time · O(L) per word, O(total letters) for all of themSpace · O(total letters) in the worst case, less when words share starts
  • Every letter costs one check and at most one new node, so a word of L letters costs O(L) no matter how many words are already stored. Searching and checking a prefix cost O(L) too.
  • The end-of-word marker is not optional. After inserting only "card", the path c, a, r exists, but "car" was never stored. Search must test the marker; startsWith only needs the path.
  • Words need not be leaves. "cat" and "cats" share a path, and the node after t is both a word and a parent. Do not assume the words sit at the bottom.
  • Memory is the honest cost. A node with a map holds only the letters it uses but pays for the map; an array of 26 is fast but uses 26 slots per node, even for a single child. A trie saves space only when words really share prefixes, and for plain exact lookups a hash set is smaller.
  • These pictures and files assume lowercase a to z. For other characters, use a map for the children (or map each character to an index first).
  • Autocomplete is two phases: O(L) to reach the prefix's node, then a depth-first walk over everything below it. That walk costs time proportional to the part of the trie under the node, so a short prefix with many matches takes longer than a long one.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Implement a Trie class with insert(word), search(word) and startsWith(prefix). search is true only for a word that was inserted; startsWith is true for any prefix of an inserted word.

Input

insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

Output

true, false, true, true

Approach

  1. Each node has a children map and an is_word flag. The root stands for the empty prefix.
  2. insert walks the word, creating a child wherever the letter has no edge yet, then sets is_word on the last node.
  3. search and startsWith share one walk that returns the node reached for the text, or nothing if an edge is missing.
  4. After insert("apple"), the walk for "app" succeeds but its node has no flag, so search("app") is false and startsWith("app") is true. Inserting "app" only sets the flag, so search("app") becomes true.
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:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

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

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

    def startsWith(self, prefix):
        return self._walk(prefix) is not None
Time · O(L) per callSpace · O(total letters stored)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. You insert "cat" and then "car" into an empty trie. How many nodes does it have, counting the root?
  2. Only "cart" has been inserted. What does search("car") return?
  3. A trie holds many words. What does autocomplete for the prefix "car" cost?
  4. Why can a trie take more memory than a hash set holding the same words?
  5. A trie holds "cat" and "cats". Which statement is true?

Question 1 of 5

You insert "cat" and then "car" into an empty trie. How many nodes does it have, counting the root?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Longest Word in Dictionary (opens in a new tab) (LeetCode, medium)

    Hint: A word counts only if every shorter prefix of it is also a word. Which nodes on its path carry a marker?

  2. Solve Replace Words (opens in a new tab) (LeetCode, medium)

    Hint: Put the roots in a trie, then walk each word and stop at the first end-of-word marker you meet.

  3. Solve Map Sum Pairs (opens in a new tab) (LeetCode, medium)

    Hint: A node can hold more than a flag. What could every node on a key's path remember so that a prefix sum is a single lookup?

  4. Solve Search Suggestions System (opens in a new tab) (LeetCode, medium)

    Hint: After each typed letter you are at one node. The suggestions are the first few words below it in alphabetical order.

  5. Solve Maximum XOR of Two Numbers in an Array (opens in a new tab) (LeetCode, medium)

    Hint: A trie does not need letters. Store each number's bits, and at each bit try to walk the branch that differs.

  6. Solve Word Search II (opens in a new tab) (LeetCode, hard)

    Hint: Search the board and the word list together: walk the trie as the path grows, and drop a path the moment its prefix is not in the trie.

  7. Solve Prefix and Suffix Search (opens in a new tab) (LeetCode, hard)

    Hint: One trie can answer both ends at once if each word is stored in several rotated forms. What would you put in front of the word?

  8. Solve Stream of Characters (opens in a new tab) (LeetCode, hard)

    Hint: The query is a suffix of what has arrived so far. What changes if you store the words backward and walk the stream backward?

Additional resources