Tries (Prefix Trees)

What a trie is and why it exists

A trie (also called a prefix tree) is a way to store a collection of words so that you can look them up by spelling them out one letter at a time. The name comes from the word retrieval. Most people pronounce it “try”.

Here is the problem it solves. Suppose you are building the search box on a phone. The user types c, then a, then r, and you want to instantly know: is car a real word? And also: are there any words that start with car, so you can suggest card, care, cargo? A plain list of words would force you to scan every word to answer those questions. A trie answers them by walking down a path, one letter at a time, doing a tiny amount of work per letter.

The core idea: a path from the top of the tree down to a marked point spells a word. Words that share a beginning share the same path near the top, and only branch apart where they start to differ.

Before we go further, a few plain definitions, since this lesson assumes no prior programming knowledge:

• A string is a piece of text, for example "car". A character (or char) is a single symbol in it, like c.
• A prefix is the beginning part of a word. ca is a prefix of car and of card. Every word is a prefix of itself.
• A tree is a structure made of nodes (boxes that hold information) connected by links. One node is the root (the starting point at the top). A node’s children are the nodes hanging directly below it.
• A dictionary in Python (written {}) is a lookup table that maps a key to a value. Here we map a character to the child node that character leads to.

The shape of one node

Every node in a trie holds two things:

1. children: a dictionary mapping each next character to the child node it leads to. If the node has links for a and o, then children has two entries.
2. is_end: a flag (a true/false value) that says “a word ends exactly here.” We need this because a word can be a prefix of a longer word. For example car and card share a path; the flag tells us that stopping at r is itself a complete word.

Here is a trie holding cat, car, and dog. The root at the top holds nothing itself; it is just the entry point. Nodes marked (end) are where a word finishes.

flowchart TD
    root((root))
    c((c))
    ca((a))
    cat((t end))
    car((r end))
    d((d))
    do((o))
    dog((g end))

    root -->|c| c
    c -->|a| ca
    ca -->|t| cat
    ca -->|r| car
    root -->|d| d
    d -->|o| do
    do -->|g| dog

Read it by following the arrows and collecting the letters on them. c then a then t reaches a node marked end, so cat is stored. c then a then r reaches another end node, so car is stored. Notice cat and car share the c -> a part of the path and split only at the last letter. That sharing is what makes a trie efficient: common prefixes are stored once.

Building a Trie in Python

We use two classes. A class is a blueprint for making objects that bundle data together. TrieNode is one node; Trie is the whole tree plus the operations on it.

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # True if a word ends at this node

class Trie:
    def __init__(self):
        self.root = TrieNode()  # the root holds no character itself

__init__ is the setup method that runs when you create a new object. self refers to the object being set up. So each new TrieNode starts with an empty children dictionary and is_end = False.

Insert

To insert a word, start at the root and walk down one character at a time. For each character, if there is no child for it yet, create one. Then move into that child. When the word is exhausted, mark the node you landed on as the end of a word.

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()  # create the missing link
            node = node.children[ch]            # step into the child
        node.is_end = True                      # mark the end of the word

Let me walk the code once. node starts at the root. for ch in word visits each character in order. if ch not in node.children asks the dictionary whether a link for that character already exists; if not, we add one. Then node = node.children[ch] moves our position down into that child. After the loop, node sits on the last character of the word, and we set its flag to True.

To watch insert reshape the tree, say the trie already holds cat, car, and dog, and we add card. We walk c -> a -> r, all of which already exist, so nothing new is created along the way. Here is the c branch just before the insert:

flowchart TD
    root((root))
    c((c))
    a((a))
    t((t end))
    r((r end))
    root -->|c| c
    c -->|a| a
    a -->|t| t
    a -->|r| r

At r there is no child d, so we create one and mark it as the end of a word. Only the d node is new, and r keeps its end mark because car is still a word:

flowchart TD
    root((root))
    c((c))
    a((a))
    t((t end))
    r((r end))
    d((d end))
    root -->|c| c
    c -->|a| a
    a -->|t| t
    a -->|r| r
    r -->|d| d

The important detail: adding card did not disturb car. The r node stays marked as an end. One path can hold two words, one ending at r and a longer one ending at d. That is what the flag makes possible.

Walking that same insert one line at a time makes the reuse concrete, starting from the trie that holds cat, car, dog. The “action” column says whether each link already existed or was created:

Only one new node was created, at step 4. The first three characters rode along the path that car had already built. This reuse is why tries are efficient for sets of words that share beginnings.

Search and startswith

Both of these walk down the tree the same way, following characters. The difference is only what happens at the end.

• search(word): does this exact word exist? Walk the characters; if any character has no link, the word is not there. If you reach the end, return the is_end flag, because reaching a node is not enough. The word must actually have been marked as ending there.
• startswith(prefix): does any stored word begin with this prefix? Same walk, but we do not care about the flag. If the path exists at all, some word uses it.

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_end = True

    def _walk(self, text):
        # follow the characters; return the node we land on, or None
        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_end

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

The helper _walk does the shared work: it follows the characters and returns the node it ends on, or None (Python’s “nothing here” value) if the path breaks. The leading underscore in _walk is a convention meaning “internal helper, not for outside use.”

Now a full run with expected output shown as comments:

t = Trie()
for w in ["cat", "car", "dog"]:
    t.insert(w)

print(t.search("car"))        # -> True   (car was inserted)
print(t.search("ca"))         # -> False  (path exists but not marked as a word)
print(t.search("cab"))        # -> False  (no 'b' link after 'ca')
print(t.startswith("ca"))     # -> True   (cat and car both start with 'ca')
print(t.startswith("do"))     # -> True   (dog starts with 'do')
print(t.startswith("z"))      # -> False  (nothing starts with 'z')

Look closely at search("ca") returning False while startswith("ca") returns True. Both reach the same node, the one after c -> a. Search checks its is_end flag, which is False there because ca was never inserted as a word. Startswith only checks that the node exists. This is exactly why the is_end flag has to exist.

Cost in Big-O

Big-O is a way to describe how the amount of work grows as the input grows, ignoring constant factors. O(L) means “work grows in proportion to L.” Here L is the length of the word or prefix being handled, and A is the size of the alphabet (26 for lowercase English letters).

Every operation walks one node per character, and looking up or inserting one entry in a Python dictionary is O(1) on average (constant time, independent of how many entries exist). So the work is one constant-time step per character: O(L) total.

Notice what is not in that table: the number of words already stored. Searching a trie holding ten words and one holding ten million words both cost O(L) for a word of length L. The lookup time depends on the word, not on how full the trie is. That is the trie’s headline advantage.

Total space for the whole trie is O(total characters across all words) in the worst case, but shared prefixes are stored once, so in practice a trie over related words is more compact than that bound suggests.

Where tries are used

• Autocomplete and type-ahead search. Walk to the node for what the user typed, then explore everything below it to list the possible completions. The startswith walk is the first half of that.
• Prefix matching and validation. Check whether a typed string is a valid prefix of any allowed word, useful in command-line tools and form fields.
• Spell checkers and word games. Fast membership tests over a fixed dictionary of valid words.
• IP routing and phone-number prefixes. The same idea works with digits or bits, not just letters.

Common pitfalls

• Forgetting the is_end flag. Without it you cannot tell a stored word from a mere prefix. search("ca") would wrongly return True just because the path to a exists. Reaching a node is necessary but not sufficient; the flag is what confirms a word ends there.
• Confusing search with startswith. They walk identically but decide differently. Search checks the flag at the end; startswith only checks that the path exists. Mixing them up is the most common trie bug.
• Reusing one node for two words by accident. Each TrieNode() must be its own object. If you wrote node.children[ch] = shared_node, different branches would corrupt each other. In the code above each missing link gets a fresh TrieNode(), which is correct.
• Empty string. Inserting "" runs the loop zero times and sets is_end = True on the root itself. Decide whether your application should allow that; it is legal but easy to overlook.
• Case and characters. Car and car are different because C and c are different characters. If you want case-insensitive matching, convert the word to lowercase before inserting and searching.

Practice

1. Add a method count_words(self) that returns how many complete words the trie holds. Hint: visit every node and count the ones where is_end is True.
2. Add a method all_with_prefix(self, prefix) that returns a list of every stored word beginning with prefix. Walk to the prefix node first, then collect the letters along every downward path that reaches an end.
3. Trace on paper what the trie looks like after inserting to, tea, ten, ted, i, in, inn. Which nodes are marked as ends, and which characters are shared between words?