Introduction to Trie

A Trie stores a set of strings by sharing common prefixes as a single walked path through a tree, so that inserting, searching, or checking a prefix costs time proportional only to the length of the string being processed, never to how many other strings are stored.

Recognize the pattern

• Problem talks about a dictionary of words and repeated prefix lookups: autocomplete, spell-check, IP routing (longest prefix match), T9 predictive text.
• You need "does any word start with X?" or "list all words with prefix X" — a hash set can answer exact membership but not prefix queries efficiently.
• Many strings share long common prefixes (e.g. "car", "cat", "cart", "care") — storing each fully is wasteful.
• You see phrases like "longest common prefix", "word break using dictionary", "search with wildcard '.'".

Brute force to optimal

Brute force: keep all words in an array/hash set. Exact search is O(1) average (hash) or O(n) (array), but a prefix query — "find all words starting with 'ca'" — requires scanning every one of the n words and checking startsWith, costing O(n·L) where L is average word length. Autocomplete-as-you-type triggers this scan on every keystroke.

Optimal (Trie): walk one edge per character from the root. Insert, search, and prefix-check all cost O(L) — independent of how many words n are stored. The trade-off is memory: each node reserves space for every possible next character (e.g. 26 pointers), so a sparse alphabet wastes space unless you use a hashmap per node instead of a fixed array.

Complexity, derived

Let L = length of the word being inserted/searched, Σ = alphabet size (26 for lowercase English), N = total characters across all stored words.

• Insert: for each of the L characters, do O(1) work (array index or hashmap lookup) to move to or create the child node → O(L) time. Node creation happens at most L times per insert.
• Search / startsWith: same walk, no creation → O(L) time.
• Space: worst case (no shared prefixes) each inserted word creates up to L new nodes, each holding Σ pointers → O(N·Σ) space overall, but shared prefixes reduce the actual node count below the sum of word lengths. Using a HashMap<Character,Node> instead of a fixed array trades a constant-factor slowdown (hash overhead) for O(1)-per-node space proportional to actual children present, not Σ.

Worked example: insert {"car", "cat", "cart"}, then search "cat" and prefix "ca"

Only 5 nodes were created (plus the pre-existing root, 6 nodes total) for 10 characters of input — the shared "ca" prefix was stored once.

Java implementation

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    private final TrieNode root = new TrieNode();

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

    public boolean search(String word) {
        TrieNode node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private TrieNode walk(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}

Trie Memory Optimization: Radix Trees & Ternary Search Trees

While standard Tries offer optimal time complexity, they are notoriously memory-inefficient. In a 64-bit JVM, each standard TrieNode object has object header overhead (16 bytes) plus a 26-pointer array references (104 bytes), meaning a naive Trie node uses at least 120 bytes of heap space just to store a single letter. At scale, this causes significant memory pressure. Production systems use two primary optimizations to mitigate this:

1. Radix Tree (Compressed Trie):
   • Mechanism: A Radix Tree compresses a Trie by merging any node that has only a single child into its parent node. The edges hold string labels rather than single characters. For example, instead of storing individual nodes for c → a → r → t, the path is collapsed into a single node with the edge label "cart".
   • Trade-off: It drastically reduces the number of tree nodes and pointer lookups, making it highly memory-efficient and cache-friendly for long, non-branching strings. This is the industry standard for IP routing tables (longest prefix match) and URL routers.
2. Ternary Search Tree (TST):
   • Mechanism: A Ternary Search Tree blends the space efficiency of a Binary Search Tree (BST) with the prefix capabilities of a Trie. Each node contains a single character and exactly three pointers: left, mid, and right.
     • If the query character is smaller than the node's character, go left.
     • If it is larger, go right.
     • If it matches, go mid and advance to the next character in the query string.
   • Trade-off: Instead of reserving Σ = 26 or 256 pointers per node, a TST node uses exactly 3 pointers, reducing the space complexity to O(N) (proportional to the number of stored characters). Lookups cost O(L + log V) time due to BST searches at each level, trading a slight constant-factor speed penalty for enormous memory savings.

Pitfalls

• Confusing search with startsWith: a node existing on the path does not mean a word ends there — always check isEnd for exact match.
• Fixed-size array waste: using 26-pointer arrays for Unicode or sparse alphabets burns memory; switch to a hashmap per node when the alphabet is large or usage is sparse.
• Ignoring node memory footprint: naive trie nodes are pointer-heavy; for memory-constrained clients, a Ternary Search Tree or Radix Tree should be used instead of a standard Trie.
• Deletion bugs: naively deleting a node can break other words sharing its prefix (e.g. deleting "car" must not remove the "c"/"ca" nodes shared with "cat"). Only prune nodes bottom-up while they have no children and are not `isEnd` for another word.
• Case sensitivity: mixing upper/lowercase without normalizing breaks the fixed `c - 'a'` index mapping.

When to use / when not

Use a Trie when you repeatedly query prefixes over a static or growing set of strings — autocomplete, spell-checkers, IP routing tables, word-search boards with dictionary pruning.

Vs. HashSet<String>: a hash set gives O(1) exact membership but cannot answer "all words starting with X" without an O(n) scan; a Trie answers it in O(L + results). If you never need prefix queries, a hash set is simpler and often more memory-efficient — don't reach for a Trie just to check membership.

Vs. sorted array + binary search: binary search gives O(L log n) prefix range lookup with far less memory overhead (no per-node pointer arrays), a reasonable choice when the dictionary is static and memory is tight.

Takeaways

• A Trie trades memory (pointer-heavy nodes) for time (O(L) operations independent of dictionary size) by sharing common prefixes as shared tree paths.
• Every node needs an explicit end-of-word flag — the path existing is not the same as a word ending there.
• Choose array-backed nodes for small fixed alphabets, hashmap-backed nodes for large/sparse alphabets.

Recall: Why is a Trie's search/insert cost O(L) regardless of how many total words are stored, while a naive prefix scan over an array of words costs O(n·L)?

Compiled from standard trie/prefix-tree references (CLRS-style tree traversal analysis; Sedgewick & Wayne, Algorithms, 4th ed., ternary/prefix tries chapter) and common interview-prep treatments of trie operations.