Tries

Back to DSA & Algorithms/00 - Roadmap Overview

---

What is a Trie?

A Trie (pronounced "try") is a tree where each node represents a character, and paths from root to nodes spell out strings. Also called a prefix tree because it's optimized for prefix lookups.

Visualization

Storing the words: "app", "apple", "api", "bat"

        (root)
        /    \
       a      b
       |      |
       p      a
      / \     |
     p   i    t ←(end: "bat")
     |   ↑
     l   (end: "api")
     |
     e ←(end: "apple")
     ↑
    (end: "app")

Shared prefixes ("app" and "apple" share "app") save space.

When to Use a Trie

Complexity

---

Core Implementation

java
class TrieNode {
    HashMap<Character, TrieNode> children; // char → TrieNode
    boolean isEnd;                         // Marks end of a complete word

    TrieNode() {
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}

class Trie {
    private TrieNode root;

    Trie() {
        this.root = new TrieNode();
    }

    /** Add a word to the trie. */
    void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());  // Create new path
            }
            node = node.children.get(ch);                // Move down
        }
        node.isEnd = true;                               // Mark word end
    }

    /** Check if exact word exists. */
    boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEnd;    // Must be a complete word
    }

    /** Check if any word starts with this prefix. */
    boolean startsWith(String prefix) {
        return findNode(prefix) != null;      // Don't need isEnd check
    }

    /** Walk the trie following the prefix. Return last node or null. */
    private TrieNode findNode(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return null;     // Path doesn't exist
            }
            node = node.children.get(ch);
        }
        return node;
    }
}

// Usage:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");      // true
trie.search("app");         // false (not marked as end)
trie.startsWith("app");    // true (prefix exists)
trie.insert("app");
trie.search("app");         // true (now it's marked as end)

Why children is a HashMap, Not an Array

You'll see two approaches:

java
// HashMap approach (flexible, used above)
HashMap<Character, TrieNode> children = new HashMap<>();  // Only creates nodes that exist

// Array approach (fixed alphabet, slightly faster)
TrieNode[] children = new TrieNode[26];  // One slot per letter
// Access: children[ch - 'a']

// HashMap is better for interviews: cleaner code, works with any character set.
// Array is better for competitive programming: slightly faster due to no hashing.

---

Pattern 1: Implement & Use Trie

Problems

• 208. Implement Trie (Prefix Tree) - Medium
• 211. Design Add and Search Words Data Structure - Medium

Search with Wildcards (Problem 211)

java
// "a.c" should match "abc", "adc", "azc", etc.
// The dot '.' matches any single character.

boolean searchWithWildcard(String word) {
    return dfs(root, word, 0);
}

private boolean dfs(TrieNode node, String word, int i) {
    if (i == word.length()) {
        return node.isEnd;
    }

    char ch = word.charAt(i);
    if (ch == '.') {
        // Try every child
        for (TrieNode child : node.children.values()) {
            if (dfs(child, word, i + 1)) {
                return true;
            }
        }
        return false;
    } else {
        if (!node.children.containsKey(ch)) {
            return false;
        }
        return dfs(node.children.get(ch), word, i + 1);
    }
}

// "." forces DFS branching — in the worst case, this explores all nodes.
// But with specific characters, it follows a single path (fast).

---

Pattern 2: Word Search II (Trie + Backtracking)

What it is

This is the hardest and most important trie problem. You have a 2D grid of letters and a list of words. Find all words from the list that exist in the grid (adjacent cells, each cell used once per word).

Why Use Trie Here?

Without trie: For each word, search the entire grid → O(words × rows × cols × 4^word_len). With trie: Search the grid once, and the trie tells you which words you're building → much faster.

java
class TrieNodeWithWord {
    HashMap<Character, TrieNodeWithWord> children = new HashMap<>();
    String word = null;  // Store complete word at the end node
}

List<String> findWords(char[][] board, String[] words) {
    // Step 1: Build trie from all words
    TrieNodeWithWord root = new TrieNodeWithWord();
    for (String word : words) {
        TrieNodeWithWord node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNodeWithWord());
            }
            node = node.children.get(ch);
        }
        node.word = word;
    }

    List<String> result = new ArrayList<>();
    int rows = board.length, cols = board[0].length;

    // Step 2: DFS from every cell, guided by trie
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    // Step 3: Start DFS from every cell
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            backtrack(board, r, c, root, result, rows, cols, dirs);
        }
    }

    return result;
}

void backtrack(char[][] board, int r, int c, TrieNodeWithWord node,
               List<String> result, int rows, int cols, int[][] dirs) {
    char ch = board[r][c];
    if (!node.children.containsKey(ch)) {
        return;  // No word in trie follows this path
    }

    TrieNodeWithWord nextNode = node.children.get(ch);

    if (nextNode.word != null) {
        result.add(nextNode.word);
        nextNode.word = null;  // Avoid duplicates
    }

    board[r][c] = '#';  // Mark visited

    for (int[] dir : dirs) {
        int nr = r + dir[0], nc = c + dir[1];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#') {
            backtrack(board, nr, nc, nextNode, result, rows, cols, dirs);
        }
    }

    board[r][c] = ch;  // Unmark (backtrack)

    // Optimization: prune trie branch if no more words below
    if (nextNode.children.isEmpty()) {
        node.children.remove(ch);
    }
}

The Pruning Optimization

After finding a word, if a trie node has no more children, remove it. This prevents revisiting dead branches and significantly speeds up the solution.

Problems

• 212. Word Search II - Hard

---

Pattern 3: Prefix Operations

java
// Longest Common Prefix
String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }

    // Build trie
    Trie trie = new Trie();
    for (String s : strs) {
        if (s.isEmpty()) {
            return "";  // Empty string → no common prefix
        }
        trie.insert(s);
    }

    // Walk the trie while there's exactly one child and it's not a word end
    StringBuilder prefix = new StringBuilder();
    TrieNode node = trie.root;
    while (node.children.size() == 1 && !node.isEnd) {
        Map.Entry<Character, TrieNode> entry = node.children.entrySet().iterator().next();
        prefix.append(entry.getKey());
        node = entry.getValue();
    }

    return prefix.toString();
}

// Note: For this specific problem, a simpler approach (compare character by character)
// is fine. Trie is overkill here but illustrates the concept.

Problems

• 14. Longest Common Prefix - Easy
• 720. Longest Word in Dictionary - Medium

---

Things You MUST Be Aware Of

1. search vs startsWith

java
// search("app")      → does the EXACT word "app" exist? Check isEnd
// startsWith("app")  → does ANY word start with "app"? Don't check isEnd

// Confusing these is a common mistake.

2. Memory Usage

java
// Tries can use a LOT of memory. Each node holds a HashMap/array of children.
// For 26 lowercase letters with array approach: each node = 26 pointers
// 100k words × 10 avg length × 26 pointers = a lot
//
// HashMap approach is more memory-efficient (only stores existing children).

3. When NOT to Use Trie

java
// If you only need exact lookups → use a HashSet (simpler, faster)
// If you only need to count prefixes → a sorted array with binary search works
// Trie shines specifically for PREFIX operations and word-by-word search

4. Storing Complete Words

java
// Instead of just isEnd = true, you can store the actual word:
node.word = "apple";
// This avoids having to reconstruct the word by tracing back from a leaf.
// Very useful in Word Search II.

---

Decision Guide

"Implement autocomplete / prefix search"
  └── Trie

"Find all words in a grid from a dictionary"
  └── Trie + Backtracking (Word Search II)

"Check if word matches pattern with wildcards"
  └── Trie with DFS on '.' wildcards

"Just check if word exists in a set"
  └── HashSet (don't overthink it)

"Longest common prefix"
  └── Simple comparison is fine, trie is overkill