TLDR: A Trie stores strings character by character in a tree, so every string sharing a common prefix shares those nodes. Insert and search are O(L) where L is the word length. Tries beat HashMaps on prefix queries — startsWith in O(L) with zero collision overhead. The canonical interview implementation uses a 26-element children array and an isEndOfWord flag.

---

📖 How Google Autocomplete Responds in Microseconds

Google's autocomplete suggests completions as you type — in milliseconds, across a vocabulary of billions of words. The question is not just "does this word exist?" — it is "give me every word that starts with this prefix." A HashMap answers the first question in O(1) but answers the second in O(n) by scanning every entry. A Trie answers both in O(L), where L is the length of the prefix.

The Trie's secret is structure. Instead of storing each word as a flat key, a Trie stores words character by character along a tree path. Every string sharing a common prefix literally shares the same nodes in the tree. Querying for all words starting with "car" means walking to the "c" → "a" → "r" node and collecting every path below it — no scanning, no hashing, just pointer traversal.

This property makes Tries irreplaceable for prefix-heavy workloads:

For exact lookups where prefix queries never occur, a HashMap is faster and simpler. The Trie is not a general-purpose replacement — it is a specialized tool that dominates a specific class of problems.

---

🔍 Each Node Is a Character: The Trie Mental Model

The intuition: each node in a Trie represents one character position in a string. The root represents the empty string. Every edge from a parent to a child represents one character. A path from the root to a node spells out the prefix formed by all edges on that path.

Consider inserting the words: car, card, care, cart, cat.

• All five words share the path c → a.
• After c → a, words split: r (for car/card/care/cart) or t (for cat).
• After c → a → r, words split again: end (car), d (card), e (care), t (cart).

The isEndOfWord flag marks nodes that terminate a valid word. Node r in the c → a → r path is marked isEndOfWord = true (for "car") even though it also has children (for card, care, cart).

This shared-prefix structure means inserting 1,000 words starting with "inter" costs the same as inserting 5 "inter" characters once — the shared prefix uses the same nodes regardless of how many words share it.

---

⚙️ TrieNode and Trie in Java: Insert, Search, and StartsWith

The canonical implementation uses a fixed-size children array of 26 slots (one per lowercase English letter) rather than a HashMap<Character, TrieNode>. The array uses more memory per node but gives O(1) child lookup with no hash computation or collision handling.

public class Trie {

    // Each node holds 26 possible children (a–z) and an end-of-word marker
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    private final TrieNode root = new TrieNode();

    // Insert a word into the Trie — O(L) where L = word.length()
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();   // Create node on demand
            }
            node = node.children[idx];
        }
        node.isEndOfWord = true;    // Mark end of this word
    }

    // Search for an exact word — returns true only if word was inserted
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;  // Prefix not found
            node = node.children[idx];
        }
        return node.isEndOfWord;  // Prefix exists; check it ends a word
    }

    // Check if any inserted word starts with this prefix
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;   // Reaching here means the prefix path exists
    }
}

The critical distinction between search and startsWith: both walk the same path character by character. They differ only in the final check. search requires node.isEndOfWord == true — the node must terminate a word. startsWith returns true as soon as the path is found, regardless of whether the node marks a word end.

---

🧠 Deep Dive: Trie Memory Layout and Prefix Query Performance

Trie Internals: The children Array and isEndOfWord Flag

Each TrieNode object in the canonical implementation holds:

• children[26]: 26 object references (8 bytes each on 64-bit JVM with compressed OOPs = 208 bytes per node, before object header overhead). Most entries are null.
• isEndOfWord: 1 boolean (1 byte, padded to 8 bytes in JVM).

A Trie for 10,000 English words can easily use 5–50 MB of heap space — far more than a HashSet<String> for the same words. This is the main cost of the fixed-array Trie.

The Trie's memory cost is justified when prefix queries are frequent. If your workload is 99% exact lookups and 1% prefix queries, use a HashSet.

The isEndOfWord flag solves an ambiguity: When inserting "car" and "card", the node for "r" in the path c → a → r must simultaneously represent a complete word ("car") and an intermediate node on the path to "card". Without the flag, there is no way to distinguish "we passed through this node" from "a word ends here."

Performance Analysis: O(L) Operations and Memory Trade-offs

Time Complexity:

• insert(word): O(L) — one node traversal or creation per character.
• search(word): O(L) — one node traversal per character.
• startsWith(prefix): O(L) — same as search, without the end-of-word check.
• getAllWordsWithPrefix(prefix): O(L + W × L_avg) where W is the number of matching words and L_avg is their average length — a DFS from the prefix node.

Space Complexity: O(A × L × N) where A is the alphabet size (26), L is the average word length, and N is the number of words. In the worst case (no shared prefixes), every word creates L unique nodes, each holding 26 pointers.

Optimization — compressed trie (Patricia trie / Radix tree): Instead of one node per character, a compressed trie stores substrings on edges. A path with no branching (c → a → r) becomes a single edge labeled "car". This reduces node count dramatically for sparse tries. Java's java.util.TreeMap with string keys uses a related idea — but the full Patricia trie is the structure behind Linux kernel routing tables and nginx URL matching.

---

📊 Trie Structure for car, card, care, cart, cat

A visual walkthrough of exactly which nodes are created and which share prefixes:

graph TD
    Root(["(root)"])
    C(["c"])
    A(["a"])
    R(["r ✓ isEnd"])
    T_cat(["t ✓ isEnd"])
    D(["d ✓ isEnd"])
    E(["e ✓ isEnd"])
    T_cart(["t ✓ isEnd"])

    Root --> C
    C --> A
    A --> R
    A --> T_cat
    R --> D
    R --> E
    R --> T_cart

    style Root fill:#607D8B,color:#fff
    style C fill:#2196F3,color:#fff
    style A fill:#2196F3,color:#fff
    style R fill:#4CAF50,color:#fff
    style T_cat fill:#4CAF50,color:#fff
    style D fill:#FF9800,color:#fff
    style E fill:#FF9800,color:#fff
    style T_cart fill:#FF9800,color:#fff

Words stored: car (R node), card (D node), care (E node), cart (T_cart node), cat (T_cat node).

The five words use 8 nodes total instead of 5 separate hash table entries. The prefix ca is shared by all five words — it costs 2 nodes regardless of how many words share it. A startsWith("car") query walks 3 nodes and returns true without touching any other word's nodes.

---

🌍 Where Tries Power Real Systems

Type-ahead search in search engines: Google, Bing, and Elasticsearch all use trie-based prefix indexes for autocomplete suggestions. The trie is typically augmented with a frequency score at each terminal node so the autocomplete system can return the most popular completions first (Priority Queue + Trie = Search Autocomplete System).

IP routing — longest prefix match: Network routers match destination IP addresses against routing table entries using a binary trie where each bit of the IP address is one level of the tree. The router walks the trie bit by bit, keeping track of the most specific route (longest prefix) that matches. This is why ip route 10.0.0.0/8 and ip route 10.1.0.0/16 can coexist — the /16 entry is deeper in the trie and wins for matching traffic.

Spell checkers and predictive text: Mobile keyboards use tries augmented with frequency data and edit-distance pruning. When you type "teh", the spell checker runs a bounded DFS through the trie, allowing up to k character substitutions, finding candidates like "the" within O(26^k × L) operations — fast enough for single-character mistakes in real time.

---

⚖️ Trie vs HashMap: When Prefix Queries Tip the Balance

The Trie vs HashMap decision is not about which is "better" — it is about which operation dominates your workload.

Trie wins when:

• You need startsWith or any prefix-based enumeration. A HashMap requires scanning all O(n) keys.
• You need to autocomplete or suggest completions — O(L + results) from a Trie vs O(n × L) scan from a map.
• Memory is not a hard constraint and keys share many prefixes (long common-prefix strings maximize sharing).

HashMap wins when:

• Workload is 100% exact key lookups — HashMap's O(1) amortized beats Trie's O(L) for short words.
• Keys are arbitrary and share few prefixes — every Trie node is unique and memory is wasted on sparse children arrays.
• You need to delete entries frequently — Trie deletion requires traversal to the terminal node and pruning upward, which is more complex than HashMap's O(1) remove.

The practical threshold: If more than 10–15% of your read queries are prefix queries, benchmark a Trie. Below that threshold, HashMap + linear scan is often faster in practice because CPU cache behavior on a flat HashMap beats pointer-chasing through a deep Trie.

---

🧭 When to Use Trie vs HashMap vs Sorted Array

---

🧪 Three Classic Trie Problems with Full Java Solutions

Example 1: Implement Trie — LeetCode 208

The full Trie class above is the canonical solution. In interviews, emphasize the search vs startsWith distinction: both walk the same path, but search requires isEndOfWord == true at the final node.

Example 2: Word Search II — Find All Words in a Board (LeetCode 212)

Build a Trie from the word list, then DFS every board cell. The Trie prunes the search: if the DFS prefix does not exist in the Trie, abandon that path immediately instead of exhaustively exploring it.

import java.util.*;

public class WordSearchII {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;   // Non-null when this node ends a complete word
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();
        int rows = board.length, cols = board[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dfs(board, r, c, root, result);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return; // Prune

        node = node.children[ch - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null;   // De-duplicate: remove word after first match
        }

        board[r][c] = '#';  // Mark visited in-place
        dfs(board, r + 1, c, node, result);
        dfs(board, r - 1, c, node, result);
        dfs(board, r, c + 1, node, result);
        dfs(board, r, c - 1, node, result);
        board[r][c] = ch;   // Restore cell
    }

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) node.children[idx] = new TrieNode();
                node = node.children[idx];
            }
            node.word = word;  // Store full word at terminal node
        }
        return root;
    }
}

Storing the full word at the terminal node (instead of a boolean flag) eliminates the need to reconstruct the word from the DFS path — a clean trick for this problem.

Example 3: Design Search Autocomplete System (LeetCode 642)

Combines a Trie with frequency tracking. Each terminal node stores a frequency count; the input(char) method incrementally walks the Trie and returns the top 3 completions by frequency using a priority queue.

import java.util.*;

public class AutocompleteSystem {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[128]; // ASCII range for all chars
        Map<String, Integer> counts = new HashMap<>(); // word → frequency
    }

    private final TrieNode root = new TrieNode();
    private TrieNode current;          // Tracks current position while typing
    private final StringBuilder input = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        current = root;
        for (int i = 0; i < sentences.length; i++) {
            insert(sentences[i], times[i]);
        }
    }

    private void insert(String sentence, int count) {
        TrieNode node = root;
        for (char c : sentence.toCharArray()) {
            if (node.children[c] == null) node.children[c] = new TrieNode();
            node = node.children[c];
            node.counts.merge(sentence, count, Integer::sum);
        }
    }

    public List<String> input(char c) {
        if (c == '#') {
            // End of input: record the typed sentence
            insert(input.toString(), 1);
            input.setLength(0);
            current = root;
            return Collections.emptyList();
        }

        input.append(c);
        if (current == null || current.children[c] == null) {
            current = null;
            return Collections.emptyList();
        }
        current = current.children[c];

        // Return top 3 completions by frequency (lexicographic tiebreak)
        return current.counts.entrySet().stream()
                .sorted((a, b) -> a.getValue().equals(b.getValue())
                        ? a.getKey().compareTo(b.getKey())
                        : b.getValue() - a.getValue())
                .limit(3)
                .map(Map.Entry::getKey)
                .collect(java.util.stream.Collectors.toList());
    }
}

---

🛠️ Apache Lucene's Term Dictionary: A Compressed Trie at Scale

Apache Lucene (the search engine powering Elasticsearch and Solr) uses a Finite State Transducer (FST) — a compressed trie — as its term dictionary. Every unique term (word) in the index is stored as a path in the FST.

The FST is Lucene's answer to the Trie memory problem: instead of 26 children per node, Lucene's FST stores only the edges that actually exist, in a compact byte-array representation. A Lucene index with 1 million unique terms uses roughly 5–20 MB for the FST — far less than the 500+ MB a naive 26-children Trie would require.

Lucene's org.apache.lucene.util.fst.FST class exposes the core operations:

// Conceptual usage — building a term dictionary FST (simplified)
import org.apache.lucene.util.fst.*;
import org.apache.lucene.util.BytesRef;

// FST maps BytesRef (term bytes) to output values (document frequencies, offsets)
// Built via Builder, which requires terms to be added in sorted order
Builder<Long> builder = new Builder<>(FST.INPUT_TYPE.BYTE1, PositiveIntOutputs.getSingleton());
builder.add(new BytesRefBuilder().toBytesRef(), 0L); // internal operation

// The resulting FST supports prefix lookup, range enumeration, and fuzzy search
// all in O(L) per query — the same asymptotic bound as a Trie

Lucene's prefix query (PrefixQuery) walks the FST to find the prefix node, then enumerates all terms below it — exactly the getAllWordsWithPrefix operation on a Trie, running in O(L + matching terms).

For a full exploration of Lucene's inverted index architecture, see the companion post on How Lucene Works.

---

📚 Lessons Learned: Trie Implementation Pitfalls

1. search vs startsWith differ only in the final check. Both walk identical paths. The bug is checking isEndOfWord in startsWith (which rejects valid prefixes that don't end a word) or forgetting to check it in search (which falsely reports prefixes as words). Keep the two methods side by side to see the single-line difference.

2. The fixed 26-children array wastes memory for sparse vocabularies. If your word list contains Unicode characters, special characters, or only a small subset of letters, use HashMap<Character, TrieNode> for children instead. The access is O(1) amortized but avoids allocating 26 null pointers per node.

3. Populate node.word at terminal nodes for Word Search II. Storing the full word string at the terminal node eliminates expensive path-reconstruction during DFS. This is always preferable to re-building the word by traversing back up the Trie.

4. De-duplicate Word Search II results by nulling node.word after the first match. Without this, the same word can be collected multiple times if it appears in multiple starting cells on the board.

5. Trie deletion is non-trivial. Deleting a word requires finding the terminal node, clearing isEndOfWord, and then pruning all ancestor nodes that have no other children and no other word endings. Forgetting the pruning step leaves orphaned nodes and leaks memory. For interview problems, deletion is rarely asked — but in production Trie implementations, always implement it.

---

📌 Summary: Trie Mastery in Five Key Points

• A Trie stores strings character by character, sharing nodes for all strings with a common prefix. This structural sharing makes prefix queries O(L) regardless of how many strings are stored.
• insert, search, and startsWith are all O(L) — linear in the length of the word or prefix, not in the total number of stored words.
• The isEndOfWord flag distinguishes prefixes from complete words. Without it, searching for "car" in a Trie that contains "card" would return a false positive.
• Trie beats HashMap for prefix queries; HashMap beats Trie for exact-only lookups. The crossover point is roughly 10–15% prefix query share in the workload.
• Production tries are compressed (Patricia trie, Radix tree, FST) to reduce the memory overhead of the sparse children array. Apache Lucene's FST reduces memory by 10–100× compared to a naive trie.

Use a Trie when your problem involves prefix matching, autocomplete, or pruning DFS on a word grid. For exact lookups with no prefix semantics, a HashMap is simpler and faster.

---

📝 Practice Quiz

1. A Trie is built from the words ["car", "card", "care", "cat"]. A search("car") call returns what result, and why does a startsWith("car") call return a different conceptual answer for a word not in the Trie?

   • A) search("car") returns false because "car" is a prefix of "card"; startsWith("car") also returns false
   • B) search("car") returns true because the "r" node in path c→a→r has isEndOfWord=true; startsWith("car") also returns true but for any prefix, not just word boundaries
   • C) Both always return the same result because they traverse the same path Correct Answer: B

2. You need to implement Word Search II, which finds all valid words from a dictionary that can be formed by adjacent board cells. A brute-force approach runs DFS for every word in the dictionary. What does building a Trie from the dictionary first enable, and how does it change the worst-case search cost?

   • A) Nothing — DFS must explore every cell regardless
   • B) The Trie lets you prune DFS paths the moment the current board prefix has no matching Trie node, eliminating entire subtrees without exploring them
   • C) The Trie replaces DFS entirely — you search the Trie without traversing the board Correct Answer: B

3. You are choosing between a Trie with fixed children[26] arrays and a Trie with HashMap<Character, TrieNode> children. Your vocabulary is 500 technical terms using only lowercase letters a–z. Which implementation is preferable, and why?

   • A) HashMap children — technical terms share few prefixes, so HashMap avoids 26-slot allocation per node
   • B) Fixed children[26] array — constant-time O(1) child access, predictable memory layout, and all 26 letters are potentially used in technical vocabulary
   • C) Neither — a sorted array of strings with binary search is always better for 500 words Correct Answer: B

4. (Open-ended challenge) A standard Trie uses a 26-element children array, consuming ~208 bytes per node on a 64-bit JVM. Describe the Patricia trie (compressed trie) compression strategy. How does it reduce node count, and what trade-off does it introduce when inserting a new word that partially matches an existing compressed edge label? Illustrate with the example of inserting "ca" into a Trie that already contains a compressed edge "car".

---

🔗 Related Posts

• BFS — Breadth-First Search
• DFS — Depth-First Search
• Binary Search Patterns