Tries — Prefix Trees Built for Strings

A trie (pronounced “try,” short for retrieval) is a tree where edges represent characters and paths from root to a marked node represent complete words. It is not a hash map of strings — it’s a tree of characters that physically encodes shared prefixes. That structural difference is what gives it capabilities no flat hash map can match.

The defining use case: given a dictionary of 100,000 words, answer “does any word start with ‘pre’?” A hash map requires scanning every key. A trie answers in O(3) — one step per character in the prefix. That O(L) complexity for any prefix-related query is the trie’s fundamental value.

Trie Structure

Words inserted: ["apple", "app", "ape"]

         root
          |
          a
          |
          p
         / \
        p   e
        |   |
        l  (end="ape")
        |
        e
        |
       (end="apple")
      (also end="app" at second 'p')

Each node stores:

  1. An array (or map) of child nodes — one slot per possible character

  2. A boolean isEnd — marks whether a complete word terminates at this node

class TrieNode {
    TrieNode[] children;
    boolean isEnd;

    TrieNode() {
        children = new TrieNode[26];   // for lowercase a-z
        isEnd = false;
    }
}

class Trie {
    private final TrieNode root = new TrieNode();
    // insert, search, startsWith below
}

Core Operations

Insert — O(L)

Walk the trie character by character. Create nodes where they don’t exist. Mark the final node as a word endpoint.

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

Search — O(L)

Walk the trie following the word’s characters. If any character has no corresponding child, the word is not in the trie. At the end of the word, check isEnd — this distinguishes between “apple” (present) and “app” (prefix only, if “app” was never inserted separately).

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.isEnd;   // true only if a complete word ends here
}

startsWith — O(L)

Identical to search, except the final isEnd check is dropped. Any path that exists in the trie qualifies as a valid prefix.

boolean startsWith(String prefix) {
    TrieNode curr = root;
    for (char c : prefix.toCharArray()) {
        int idx = c - 'a';
        if (curr.children[idx] == null) return false;
        curr = curr.children[idx];
    }
    return true;   // the prefix path exists
}

What most people get wrong: confusing search and startsWith. The only functional difference is the final isEnd check. If only “apple” is inserted: search("app") returns false; startsWith("app") returns true. Get this mixed up on LC 208 and you fail the easy problem.

Space Complexity: The Fan-Out Problem

Each TrieNode holds 26 child pointers for lowercase English. With n nodes in the trie, that’s 26n pointer slots — most of which are null for typical input. The constant factor of 26 is real in memory even if asymptotically it’s O(n).

For Unicode or large alphabets, use a HashMap<Character, TrieNode> per node:

class TrieNodeMap {
    Map<Character, TrieNodeMap> children = new HashMap<>();
    boolean isEnd = false;
}

Trade-off:

Implementation

Space Used

Access Time

When to Use

Array [26]

26 × nodes (sparse)

O(1), direct index

Known small alphabet (a-z)

HashMap per node

proportional to actual edges

O(1) avg, hash overhead

Large or unknown alphabet

For LeetCode (typically lowercase a-z), the array implementation is cleaner and faster. For a real autocomplete system supporting Unicode, you’d use a hash map or compressed trie.

Compressed Tries / Patricia Tries (Intuition)

A standard trie has a problem with sparse paths: the word “elephant” stored alone creates a chain of 8 nodes for e-l-e-p-h-a-n-t that could be one edge labeled “elephant.”

A Patricia trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric) compresses non-branching chains into single labeled edges. A branch occurs only where two stored words diverge in their characters.

You will not implement a Patricia trie for LeetCode. Understanding that they exist explains why production systems (autocomplete backends, routing tables, DNS resolution) don’t use a naive trie with one character per node. Most use compressed variants or radix trees to control memory.

Applications

  • Autocomplete: traverse to the prefix node, then DFS to collect all isEnd nodes below — every path is a word completion suggestion

  • Spell check: search for a word; if not found, enumerate nearby words by single-character substitution or deletion

  • IP routing (longest prefix match): store network prefixes in a binary trie (bits instead of characters); longest matching prefix determines the routing decision

  • Word Search II (LC 212): combine a trie with backtracking on a grid — simultaneously match multiple dictionary words instead of searching separately for each

Word Search II: Trie + Backtracking Combined

This is the payoff problem that justifies learning tries in the context of Phase 2. LC 212 asks for all dictionary words present in a character grid.

Naive approach: for each word in the dictionary, run backtracking on the grid independently. Cost: O(W × 4^(MN)) where W is number of words.

Trie approach: insert all words into a trie. During grid backtracking, walk the trie in sync with the grid path. If the current cell’s character has no child in the current trie node, prune immediately — no word with this prefix exists.

// Key logic inside the backtracking function:
void dfs(char[][] board, int i, int j, TrieNode node) {
    char c = board[i][j];
    int idx = c - 'a';

    if (node.children[idx] == null) return;   // PRUNING: no word has this prefix

    TrieNode next = node.children[idx];
    if (next.isEnd) {
        result.add(next.word);        // found a word
        next.isEnd = false;           // avoid adding duplicates
        next.word  = null;
    }

    board[i][j] = '#';                // mark visited
    // recurse on 4 neighbors
    board[i][j] = c;                  // restore

    // Optimization: prune dead trie branches (no children left, not a word)
    if (isEmpty(next)) node.children[idx] = null;
}

Storing the complete word in each isEnd node (instead of reconstructing from path) is a practical optimization that avoids rebuilding the string from the grid path.

Practice Problems

#

Problem

Difficulty

Focus

1

LC 208 — Implement Trie

Easy

Core insert/search/startsWith

2

LC 648 — Replace Words

Medium

Trie for shortest prefix lookup

3

LC 211 — Design Add and Search Words Data Structure

Medium

Wildcard ‘.’ — DFS through all children

4

LC 212 — Word Search II

Hard

Trie + backtracking, branch pruning

Start with LC 208. Implement from scratch in 20 minutes without reference. If you can do that, you understand the structure. LC 211 adds a twist: the ‘.’ wildcard in search must try all non-null children — it’s a DFS on the trie itself. LC 212 is the boss fight for Phase 2.