Lesson 14 · Non-linear structures

Trie Operations and Applications

A Trie is a specialized tree that stores strings character by character, providing blazing fast prefix matching and autocomplete capabilities.

Sharing Prefixes

In a list of strings, many words share the same beginning (e.g., 'cat', 'car', 'cart'). A Trie capitalizes on this by merging shared prefixes into single paths. The root represents an empty string, and every subsequent edge represents a single character.

Node Structure

Instead of left and right children, a Trie node typically contains a hash map or a 26-element array pointing to its children. It also holds a boolean flag indicating whether the path from the root to this node constitutes a complete, valid word in the dictionary.

Key reference

Terms, operations, and practical uses

Structure

Prefix SharingMultiple words that start with the same sequence of letters share the exact same nodes in the tree.
Child PointersA node does not hold a character; the edge to the child represents the character. Implemented as an array of 26 or a hash map.
Terminal FlagA boolean isWord flag inside the node that is true if the path from the root to this node constitutes a valid dictionary word.

Operations

InsertionIterate through characters of a string, creating new child nodes only when a path for a character doesn't already exist.
Word SearchTraverse the characters. If a path ends or the final node's terminal flag is false, the word does not exist.
Prefix SearchTraverse the characters. If the path exists, the prefix exists. All descendant nodes represent valid autocomplete suggestions.

Variants

Radix TrieAlso known as a Patricia Trie. Compresses non-branching paths into a single edge containing a string, saving immense memory.
Bitwise TrieInstead of characters, edges represent 0 or 1. Used heavily for finding Maximum XOR pairs in arrays.
Aho-CorasickA Trie augmented with 'failure links' (similar to KMP) allowing simultaneous search for multiple patterns in a text.

Code example

Insert a word into a trie

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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
trie = Trie()
trie.insert('cat')
print('Inserted: cat')

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isWord = false;
};
class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children[c - 'a']) node->children[c - 'a'] = new TrieNode();
            node = node->children[c - 'a'];
        }
        node->isWord = true;
    }
};

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}
class Trie {
    TrieNode root = new TrieNode();
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }
}

Inputword = "cat"

OutputInserted: cat

Example

Run the example step by step

Output

O(L) Search Time

Searching for a word of length L in a Trie takes strictly O(L) time. We simply follow the character edges from the root. This performance is entirely independent of how many millions of words are stored in the tree, making it superior to hash sets for prefix operations.

Autocomplete and IP Routing

Tries are the industry standard for autocomplete systems, spell checkers, and Boggle solvers. A specialized binary version, the Radix Trie, is heavily utilized in network routers to match IP addresses against routing tables using longest-prefix matching.