Lesson 5 · Non-linear structures

Tries and Prefix Trees

A Trie (pronounced 'try') is a specialized tree that stores strings character by character. It provides blazing-fast O(L) time lookups and is the foundational data structure behind autocomplete and spell checkers.

The Path Is the Key

A trie — also called a prefix tree, and pronounced 'try' — stores strings by their characters rather than by a hash or a comparison. Each edge is labelled with a character, and the sequence of edges from the root to a node spells out a prefix.

The consequence is that no node stores a complete string. The word 'cat' is not held anywhere; it exists as the path root → c → a → t. This inverts how the other structures work: a hash table stores the key and computes where to put it, while a trie decomposes the key and lets its position be the key.

Because the path is the key, every string sharing a prefix shares that path. 'car', 'card', and 'care' descend through the same c-a-r nodes before diverging, so the common prefix is stored exactly once no matter how many words extend it.

Each node needs two things: a way to reach its children by character, and a boolean isEndOfWord flag. That flag is essential and easy to forget. Without it, storing 'card' would make 'car' appear to be stored too, since the path exists — the flag is what distinguishes a prefix exists from a word ends here.

The children mapping is the design decision that determines memory. A fixed array of size 26 for lowercase letters gives O(1) child access by c - 'a' and is fast, but allocates 26 slots per node whether used or not. A hash map per node stores only the children that exist, saving memory on sparse tries at the cost of hashing on every step.

Edges carry characters; the root-to-node path spells the prefix
No node stores a whole string — position encodes the key
isEndOfWord separates a stored word from a mere prefix
Children as a fixed array is fast; as a hash map is compact

Insertion, Search, and Deletion

Insertion walks the string one character at a time from the root. At each character, follow the existing child if present, or create a new node if not. After the last character, set isEndOfWord on the node reached. The cost is O(L) for a word of length L, and it allocates at most L new nodes.

Search walks the same path without creating anything. If any character has no matching child, the word is absent. If the walk completes, the answer depends on the flag: isEndOfWord true means the word is stored, false means only a longer word passes through here.

Prefix search — startsWith — is the same walk with the flag ignored. Completing the path proves the prefix exists, regardless of whether a word ends there. That these two differ by a single boolean check is what makes the trie the natural structure for autocomplete.

Deletion is the operation with real subtlety, because a node may be needed by other words. Walk to the end of the word and clear its isEndOfWord. Then, walking back toward the root, remove a node only if it has no children and is not itself the end of another word. Stop at the first node failing either test.

Deleting 'car' from a trie also containing 'card' illustrates why: the r node must survive because 'card' still needs it. Removing nodes unconditionally would silently destroy other stored words — the standard deletion bug.

A common simplification is to skip node removal entirely and only clear the flag. The trie then holds unused nodes but every query stays correct, and for workloads where deletion is rare this is a reasonable trade.

Trie operations, for a key of length L
Operation	Cost	Detail
Insert	O(L)	Creates at most L nodes
Search a word	O(L)	Path must exist and the flag must be set
Search a prefix	O(L)	Path must exist; flag ignored
Delete	O(L)	Prune upward only while a node is childless and not a word end
List all with a prefix	O(L + k)	Walk to the prefix, then traverse the subtree

Insert follows or creates a child per character, then sets the flag
Word search checks the flag; prefix search ignores it
Delete prunes upward only past childless, non-terminal nodes
Skipping the pruning wastes memory but stays correct

What the O(L) Bound Really Says

A trie's operations are O(L) in the length of the key, with no dependence on n, the number of stored keys. Looking up a word in a trie of ten words and one of ten million words costs the same.

That is a stronger statement than it first appears, and it is worth comparing carefully. A balanced BST of strings is O(log n) comparisons, but each string comparison is itself O(L), giving O(L log n) in reality — a bound frequently quoted as O(log n) by ignoring the comparison cost. A hash table is O(L) to compute the hash plus O(L) to verify equality on a match, so it is also O(L), and typically with a smaller constant.

So a trie does not beat a hash table at exact lookup, and choosing one for that purpose is a mistake. Its advantage is entirely in the queries a hash table cannot answer at all.

Prefix queries are the case. Finding every word beginning with 'pre' is a walk to the prefix node followed by a traversal of its subtree — O(L + k) for k results. A hash table has no notion of prefix and must examine every key, at O(n·L). This is why autocomplete, IP routing tables with longest-prefix matching, and dictionary lookups in word games all use tries.

Two further properties come free. Traversing a trie in child order yields keys in lexicographic order, so a trie is implicitly sorted. And a trie never has hash collisions, so its worst case equals its average case — no adversarial input can degrade it.

The cost is memory, and it is the reason tries are not the default. A node with a 26-slot array of 8-byte pointers is 208 bytes plus the flag, and a word of length L may allocate up to L such nodes. Storing a few thousand words can consume megabytes. Prefix sharing offsets this when the key set is dense, and helps very little when keys are unrelated.

O(L) regardless of how many keys are stored
A hash table is also O(L) for exact lookup, usually faster
Prefix queries are where a trie wins — O(L + k) against O(n·L)
Lexicographic order is free; memory is the price

Key reference

Terms, operations, and practical uses

Core vocabulary

Prefix TreeAnother name for a Trie, emphasizing its ability to store and search for prefixes.
Root NodeThe starting point of the Trie, which typically does not contain a character itself.
End-of-Word FlagA boolean property on a node indicating that the path from the root to this node forms a complete, valid word.

Structure

Child PointersLinks from a node to its possible next characters. Can be an array (size 26) or a Hash Map for flexibility.
Shared BranchesWords with the same prefix (e.g., 'car' and 'cat') share the same nodes for their common letters.
O(L) TimeThe time complexity for insertion and search, where L is the length of the word, independent of dictionary size.

Applications

AutocompleteQuickly finding all words that start with a given prefix by traversing to the prefix node and collecting all descendants.
Spell CheckerVerifying if a word exists in a dictionary, or finding the closest valid word.
IP RoutingUsing specialized binary Tries to quickly determine the longest prefix match for network routing tables.

Implementation

Insert 'cat' and 'car' into a Trie

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

root = TrieNode()
for word in ["cat", "car"]:
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_word = True
print('Trie nodes created')

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};
int main() {
    TrieNode root;
    for (const string& word : vector<string>{"cat", "car"}) {
        TrieNode* node = &root;
        for (char c : word) {
            if (!node->children.count(c))
            node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isWord = true;
    }
    cout << "Trie nodes created\n";
}

import java.util.HashMap;
class Main {
    static class TrieNode {
        HashMap<Character, TrieNode> children = new HashMap<>();
        boolean isWord;
    }
    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        for (String word : new String[]{"cat", "car"}) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.isWord = true;
        }
        System.out.println("Trie nodes created");
    }
}

Watch it run

Step through it

Running on words = ['cat', 'car']

Output

Read all 8 Steps

Initialize Trie Start with an empty root node.
Insert 'cat' Start at the root. 'c' doesn't exist, so create node 'c'.
Continue 'cat' From 'c', 'a' doesn't exist, so create node 'a'.
Finish 'cat' From 'a', 't' doesn't exist. Create node 't' and mark it as a valid word.
Insert 'car' Start at the root again. The 'c' node already exists! We reuse it.
Continue 'car' From 'c', the 'a' node also already exists! We reuse it.
Create 'r' From 'a', 'r' does not exist. We create node 'r' as a sibling to 't'.
Finish 'car' We mark 'r' as a valid word. Both 'cat' and 'car' now share the 'ca' prefix.

Compressing the Memory Cost

Two variants attack the space problem, and knowing they exist is part of understanding when a plain trie is acceptable.

A radix tree — also called a compressed trie or Patricia trie — collapses every chain of single-child nodes into one edge labelled with the whole substring. Storing only 'internationalisation' in a plain trie needs 21 nodes in a chain; a radix tree needs one edge. This removes the nodes that carry no branching information, typically shrinking the structure dramatically on sparse key sets, at the cost of more complicated insertion since an edge must sometimes be split when a new key diverges partway along it. Linux's IP routing table uses this structure.

A ternary search trie gives each node three children — less-than, equal, and greater-than — plus one character rather than an array of them. Memory drops to close to a BST's while prefix queries remain possible, and lookup becomes O(L + log n). It is a middle ground between a trie and a balanced tree.

For a fixed dictionary that never changes, a DAWG (directed acyclic word graph) merges identical suffixes as well as prefixes, turning the tree into a DAG and often cutting size by an order of magnitude. It cannot support insertion, which limits it to static sets like a spell-checker's word list.

The decision, stated simply: use a hash table for exact lookup, a balanced tree when sorted order or range queries are needed on general keys, and a trie when the queries are about prefixes. If a trie is the right answer but memory is tight, compress it to a radix tree before abandoning the approach.

Radix trees collapse single-child chains into one labelled edge
Ternary search tries trade array children for three-way branching
A DAWG merges shared suffixes too, but cannot be modified
Prefix queries justify a trie; exact lookup does not