Tries Pattern

The Tries pattern (Prefix Tree) is an alphabet-linked tree structure designed to store and search string keys efficiently. It compresses shared prefixes into single node branches to accelerate auto-complete and prefix validations.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks to verify if any word in a dictionary begins with a given prefix.
• You need to search for a large set of words in a grid of letters (e.g. Word Search II).
• The task involves building autocomplete, type-ahead, or spell-checking systems.

How It Works

Instead of storing whole strings in isolation (which makes prefix checks slow), a trie splits strings into characters. Each node contains a character dictionary (or a 26-element array for lowercase ASCII) and a boolean flag marking if the node completes a word.

• To insert "app", you start at the root. Create a node for 'a', then 'p' under 'a', then 'p' under 'p', and mark the final 'p' as a complete word.
• To insert "apple", you reuse the existing 'a' -> 'p' -> 'p' nodes, and only add 'l' -> 'e' under the second 'p'.

Complexity, With Caveats

• Time Complexity: O(L) for insert, search, and prefix matching operations, where L is the length of the string. Lookups are independent of the number of words in the dictionary.
• Space Complexity: O(N * L) where N is the number of words and L is the average length. In the worst case (no shared prefixes), every character requires a new node. Sparse arrays inside nodes can waste memory.

Minimal Code Template

public class TrieTemplate {
    public static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isWord = true;
    }

    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) return false;
            curr = curr.children[idx];
        }
        return curr.isWord;
    }
}

class TrieNode:
    def __init__(self):
        self.children = {}  # maps char -> TrieNode
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.is_word

class TrieTemplate {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isWord = false;
    };
    TrieNode* root;

public:
    TrieTemplate() {
        root = new TrieNode();
    }

    void insert(std::string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isWord = true;
    }

    bool search(std::string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return curr->isWord;
    }
};

Where This Pattern Falls Short

• Memory overhead: If you insert many distinct short words, the pointer overhead (e.g. allocating 26 pointers for every node) can consume more memory than simply storing the strings in a Hash Set.
• Suffix matching: Tries only match strings from left to right (prefixes). If you need to search for suffixes (e.g. “ends with”), a standard trie fails, and you must insert the reversed strings into the trie.

Related Patterns, Compared

• Trees: choose this instead when managing general parent-child relationships that do not represent string characters or prefix grouping.
• Hash Table: choose this instead when you only need to match exact strings and do not need prefix searches, as hash tables use less memory and run in O(L) time.

Frequently Asked Questions

Why is it called a Trie? The word comes from the word “retrieval”. It was originally pronounced “tree”, but is commonly pronounced “try” to distinguish it from a standard tree.

Can we implement a Trie with characters other than lowercase English? Yes. You can use a hash map instead of a fixed 26-element array for the children pointers, which dynamically supports any Unicode characters.

What does this pattern test in interviews? It tests your ability to design nested object structures, navigate tree pointers, and understand memory compression trade-offs.