Tries (Prefix Trees)

Introduction

Imagine you are building the Auto-Complete engine for a search bar. A user types "cat". You have a database of 10 million words, and you need to instantly return words like "catch", "caterpillar", and "catastrophe".

If you store the 10 million words in an Array, finding matches takes $O(N)$ time, grinding your server to a halt. If you use a Binary Search Tree or a Hash Table, you can find exact matches like "cat" quickly, but finding all words that start with "cat" is impossible without checking everything.

To solve this, we don’t store words as indivisible blocks. We store them letter-by-letter in a Trie (pronounced “try”, coming from the word retrieval).

The Anatomy of a Trie

A Trie is a Tree, but instead of having a left and right child, a Trie node can have up to 26 children (one for each letter of the English alphabet).

When you build a Trie, you insert words character by character. If multiple words share the same prefix, they share the exact same nodes in the tree!

Visualising a Trie

Let’s insert the words "CAT", "CAB", "CAR", and "DOG".

Notice how "CAT", "CAB", and "CAR" all share the exact same [C] and [A] nodes. This is why Tries are so incredibly space-efficient for dictionaries; the prefix "pre" might be shared by 5,000 words, but it is only stored in memory once.

(Note: The (end) marker is crucial. If we insert "CAR" and "CART", we need a boolean flag on the R node to signify that “CAR” is a valid complete word on its own, not just a prefix for “CART”).

The Java Implementation

1. The TrieNode Class

Instead of left and right pointers, we use an Array of size 26 (if we only care about lowercase English letters a-z).

class TrieNode {
    // Array of pointers to children nodes
    TrieNode[] children;
    
    // True if a complete word ends at this node
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

2. The Trie Class (Insert & Search)

To insert a word, we start at the root. We check the first character. If a child node for that character exists, we move to it. If it doesn’t, we create it. We repeat this until the word is done, and mark the final node with isEndOfWord = true.

To search for a word (or prefix), we just walk down the tree following the characters.

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    /** 
     * Insert a word into the Trie. O(L) Time where L is word length.
     */
    public void insert(String word) {
        TrieNode current = root;
        
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // Convert 'a'-'z' to 0-25
            
            // If the path doesn't exist, build it
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            
            // Move down to the next node
            current = current.children[index];
        }
        
        // Mark the end of this specific word
        current.isEndOfWord = true;
    }

    /** 
     * Returns true if the exact word is in the Trie.
     */
    public boolean search(String word) {
        TrieNode node = findNode(word);
        // We must find the node AND it must be marked as an end of word
        return node != null && node.isEndOfWord;
    }

    /** 
     * Returns true if any word in the Trie starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        // If we can traverse the path, the prefix exists!
        return findNode(prefix) != null;
    }

    /** Helper method to traverse down the Trie */
    private TrieNode findNode(String str) {
        TrieNode current = root;
        for (char c : str.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return null; // Path breaks, word doesn't exist
            }
            current = current.children[index];
        }
        return current;
    }
}

Complexity

Let $L$ be the length of the string you are inserting or searching.

Why not just use a Hash Map?

A Hash Map gives $O(1)$ lookups. But remember, a Hash Map must compute the hash of the entire string first, which actually takes $O(L)$ time. So mathematically, a Trie and a Hash Map are equally fast for exact word lookups.

The Trie wins completely on two fronts:

1. Prefix Searching: A Hash Map cannot tell you all the words that start with “app”. A Trie can do this instantly.
2. Memory: Storing 100,000 variations of prefix-heavy words in a Hash Map duplicates the string data over and over. A Trie compresses them down elegantly. (However, an extremely sparse Trie with no shared prefixes will waste memory with lots of empty children[26] arrays).

Real-World Applications

1. Auto-Complete: Type the prefix, find the Trie node, then run a Depth-First Search (DFS) down from that node to collect all possible valid endings to suggest to the user.
2. Spell Checkers: Easily find words that are “1 character off” from the inputted string by heavily pruning a DFS over the Trie.
3. IP Routing: Longest Prefix Matching algorithm for routing packets over the internet.

Practice Problems

1. Implement Trie (Prefix Tree) – LeetCode #208 — Write the exact code from above yourself to commit it to memory.
2. Design Add and Search Words Data Structure – LeetCode #211 — A step up. It introduces the . wildcard character which can match any letter, requiring a recursive DFS down your Trie.
3. Word Search II – LeetCode #212 — A famously challenging interview question combining a 2D Backtracking grid with a Trie for brutally efficient early-pruning.

Conclusion of the Series

This concludes our Algorithms Series! From the simple Big-O Notation and Bubble Sort, all the way through Dynamic Programming and Tries, you have seen the core computer science concepts that power the modern world.

The only way to truly master these is through practice. Take the LeetCode problems linked at the bottom of every post, open up an IDE, and start writing code.

Happy coding, and see you in the next series!