Tries (Prefix Trees): The Data Structure Behind Autocomplete

Scenario context

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.

Example 1: Implement Trie — LeetCode 208

The…

This walkthrough focuses on Three Classic Trie Problems with Full Java Solutions.

Before making a design choice, clarify:

• 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.

Concepts in play: tree-data-structures, jvm-internals-and-garbage-collection, sorting-and-searching-algorithms, hash-tables-and-bloom-filters

Stage 1 — 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.

Observable outcome: The Trie's secret is structure.

Stage 2 — 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.

Observable outcome: A path from the root to a node spells out the prefix formed by all edges on that path.

Stage 3 — 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.
• The critical distinction between search and startsWith : both walk the same path character by character.
• They differ only in the final check.

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

Observable outcome: They differ only in the final check.

Stage 4 — 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…
• • 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.

Observable outcome: This is the main cost of the fixed-array Trie.

Stage 5 — Trie Structure for car, card, care, cart, cat

• A visual walkthrough of exactly which nodes are created and which share prefixes: 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.

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

Observable outcome: A startsWith("car") query walks 3 nodes and returns true without touching any other word's nodes.

Stage 6 — 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.

Observable outcome: The router walks the trie bit by bit, keeping track of the most specific route (longest prefix) that matches.

End-to-end outcome

After working through the stages, you should be able to explain:

• • 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.

Alternatives considered

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.

When to Use Trie vs HashMap vs Sorted Array

When to Use Trie vs HashMap vs Sorted Array

Failure and degraded modes

Lessons Learned: Trie Implementation Pitfalls

• Detection: search vs startsWith differ only in the final check.
• User or operator impact: search vs startsWith differ only in the final check.