Tries

A Trie (prefix tree) stores strings character by character, enabling O(m) search/insert (m = word length). Each node has up to 26 children (for lowercase English). Use cases: autocomplete, spell check, prefix matching, word search. Space-efficient for shared prefixes.

Key Concepts

Deep Dive: Trie Implementation

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

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

    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.isEndOfWord = true;
    }

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

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

    private TrieNode findNode(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;
    }
}

Deep Dive: When to Use a Trie

Use Case	Why Trie?
Autocomplete	Find all words with prefix O(p + k)
Spell checker	Find similar words
IP routing	Longest prefix match
Word games	Quick word validation
Dictionary	Space-efficient storage

Trie vs HashMap: - Trie: O(m) search, supports prefix queries, space-efficient for shared prefixes - HashMap: O(1) average search, no prefix support

Common Interview Questions

• Implement Trie
• Word Search II (DFS + Trie)
• Design Add and Search Words (. matches any)
• Longest Common Prefix
• Auto-complete system