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.

What is a Trie?

A Trie is a tree whose edges or child choices represent characters. Words are formed by tracing a path from the root; a word may end at an internal node when it is also a prefix of a longer word.

Nodes also contain a boolean flag (e.g., is_word = true) to signify that the path ending at that node constitutes a complete, valid word, rather than just a prefix.

Also known as a Prefix Tree
Root node is usually empty
Words share branches if they share common prefixes

Why it is useful

A hash table supports expected constant-time bucket access, although hashing a string still reads its characters. It also cannot directly enumerate every word beginning with 'app'. A Trie reaches that prefix in O(L) time and then traverses only its descendant words.

Tries are useful for autocomplete, prefix dictionaries, routing prefixes, and word-search pruning, but they are not automatically the best choice: hash sets are often smaller and simpler for exact membership, and sorted arrays can support compact prefix ranges.

Perfect for prefix matching and autocomplete
Saves space when storing many words with shared prefixes
O(L) search time, where L is the length of the string

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.

Code example

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 <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;
    }
}

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;
        }
    }
}

Inputwords = ['cat', 'car']

OutputTrie nodes created

Example

Run the example step by step

Output

Insertion and Search

To insert a word, start at the root and look for a child node matching the first character. If it exists, move to it; if not, create it. Repeat for every character. Finally, mark the last node as a valid word.

Searching follows the exact same logic. If you ever need a character that doesn't exist among the current node's children, the word (or prefix) is not in the Trie.

Iterate character by character
Create missing nodes dynamically
Check the is_word flag at the end of a full search

Time and space costs

Time complexity for both insertion and search is exactly O(L), where L is the length of the word. This is completely independent of how many millions of words are in the Trie.

Space can be large. With map-backed children, the node count is O(total characters inserted); with a fixed child array, memory is O(number of nodes × alphabet size), even when most child slots are empty.

Insert/Search Time: O(L)
Space Complexity: O(Total characters in all words)
Pointer overhead can make Tries memory-heavy

Common mistakes

A classic mistake is forgetting the is_word boolean flag. Without it, you cannot distinguish between the valid word 'car' and the prefix 'car' inside the word 'cart'.

Another pitfall is using a fixed-size array of 26 pointers for children (for lowercase English). If you suddenly need to support uppercase, numbers, or Unicode, your array approach will break. Using a Hash Map for children is safer.

Forgetting to mark the end of valid words
Assuming the alphabet size is always exactly 26
Using Tries when Hash Sets would suffice for exact matching