Trie (Prefix Tree)

1. Introduction: The Dictionary Tree

Imagine you are building an Autocomplete engine for a search bar. A user types "app". You need to quickly suggest "apple", "application", and "apparel" out of a database of 1 million words. If you store the words in an Array, searching takes $O(N \times L)$ where $L$ is the word length. If you store them in a HashSet, you can't search by prefix at all!

The solution is a Trie (pronounced "try", from retrieval). A Trie is a specialized tree where each node represents a single character. Instead of storing the word "apple" in one node, it is stored as a path: Root -> a -> p -> p -> l -> e. Because words sharing the same prefix share the exact same nodes (apple and apparel share the a -> p -> p nodes), searching for a prefix of length $L$ takes strictly $O(L)$ time, regardless of whether you have 10 words or 10 billion words in the Trie!

2. Core Concept: The TrieNode

Unlike a Binary Tree which has exactly two pointers (left, right), a TrieNode has a pointer for every possible character. If we are only dealing with lowercase English letters, a TrieNode has an array of 26 pointers!

Crucially, the node itself does not necessarily store the character. The character is implicitly defined by the index of the array. If children[2] is not null, it means the character 'c' exists in that path. We also need a boolean flag isWord to mark the end of a valid word (e.g., "app" might be a valid word, even if the path continues to "apple").

class TrieNode {
    // Array of 26 pointers to child nodes
    public TrieNode[] children = new TrieNode[26];
    
    // True if this node represents the end of a completely inserted word
    public boolean isWord = false;
}

3. Advanced Code Example: Implement a Trie

Problem Statement: (LeetCode 208) Implement the Trie class:

• insert(String word): Inserts the string into the trie.
• search(String word): Returns true if the exact word is in the trie.
• startsWith(String prefix): Returns true if there is any previously inserted word that has the prefix.

public class Trie {
    private TrieNode root;

    public Trie() {
        // The root node is empty (represents the empty string)
        root = new TrieNode();
    }
    
    // O(L) time where L is the length of the word
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            // If the path doesn't exist, create a new node
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            // Move down the path
            curr = curr.children[index];
        }
        // Mark the very last node as a valid word endpoint
        curr.isWord = true;
    }
    
    // O(L) time
    public boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            // If the path breaks early, the word doesn't exist!
            if (curr.children[index] == null) {
                return false;
            }
            curr = curr.children[index];
        }
        // The path exists, but is it a fully inserted word? 
        // (e.g., searching "app" when only "apple" was inserted should return false)
        return curr.isWord;
    }
    
    // O(L) time
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                return false;
            }
            curr = curr.children[index];
        }
        // The path exists! We don't care if it's a full word or not.
        return true;
    }
}

4. Master Code Example: Word Search II (Trie + DFS)

Problem Statement: (LeetCode 212) Given an m x n board of characters and a list of strings words, return all words on the board. You can move horizontally or vertically.

The Brute Force Trap: For every cell, run a DFS. Check against every word in the dictionary. This is astronomically slow. The Elite Insight: Build a Trie out of the words list. Run a DFS on the board. At every step, check if the current path exists in the Trie! If the Trie path breaks (returns null), instantly abort the DFS branch! This prunes millions of useless searches.

import java.util.ArrayList;
import java.util.List;

public class WordSearchII {
    // Modified TrieNode to hold the actual word at the leaf to make collection easier!
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null; 
    }

    public List<String> findWords(char[][] board, String[] words) {
        // 1. Build the Trie
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new TrieNode();
                curr = curr.children[i];
            }
            curr.word = w; // Store the full word at the leaf
        }

        // 2. DFS from every cell on the board
        List<String> result = new ArrayList<>();
        int rows = board.length;
        int 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 curr, List<String> result) {
        // Out of bounds or already visited (we use '#' as visited marker)
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] == '#') return;
        
        char letter = board[r][c];
        TrieNode nextNode = curr.children[letter - 'a'];
        
        // PRUNING: The Trie says this prefix doesn't exist. Abort!
        if (nextNode == null) return;
        
        // We found a word!
        if (nextNode.word != null) {
            result.add(nextNode.word);
            nextNode.word = null; // Deduplication: prevent finding the same word twice
        }
        
        // Mark visited
        board[r][c] = '#';
        
        // Explore all 4 directions
        dfs(board, r + 1, c, nextNode, result);
        dfs(board, r - 1, c, nextNode, result);
        dfs(board, r, c + 1, nextNode, result);
        dfs(board, r, c - 1, nextNode, result);
        
        // Backtrack
        board[r][c] = letter;
    }
}

5. Common Mistakes Beginners Make

1. Using a HashMap for children instead of an Array

   • The Mistake: Map<Character, TrieNode> children = new HashMap<>();
   • Why it's wrong: It's not technically wrong, and is required if dealing with Unicode/UTF-8. But for standard lowercase English problems, an array of size 26 is drastically faster and uses less memory overhead than a HashMap. In interviews, always use TrieNode[26].

2. Storing the character inside the node redundantly

   • The Mistake: class TrieNode { char val; TrieNode[] children; }
   • Why it's wrong: You never actually need to read curr.val! You navigate by index (curr.children[c - 'a']). Storing the character inside the node wastes memory and proves a slight misunderstanding of how the data structure maps keys.

3. Forgetting to Deduplicate in Word Search

   • The Mistake: Finding a word in Word Search II, adding it to the result, but leaving it in the Trie.
   • Why it's wrong: If the board has multiple valid paths to construct "apple", your DFS will find it multiple times and your result list will contain duplicates. You must do nextNode.word = null; after finding it once to effectively "delete" it from the search space.

6. Interview Q&A

Q1: How do you implement Autocomplete? Answer: You startsWith(prefix) to traverse the Trie to the node representing the end of the prefix. Then, you run a standard DFS (or BFS) from that specific node to collect all reachable nodes that have isWord == true.

Q2: What is the Space Complexity of a Trie? Answer: $O(N \times L \times 26)$ where $N$ is the number of words and $L$ is the max length. Tries use a LOT of memory. If a node has only one child, it still allocates an array of 26 pointers (25 of which are null). To fix this in production, engineers use Radix Trees (Compressed Tries) which merge nodes that have only one child.

7. Practice Problems

1. Implement Trie (Prefix Tree) (LeetCode 208)
   • Goal: Master the 26-pointer node structure and string iteration.
2. Design Add and Search Words Data Structure (LeetCode 211)
   • Hint: How do you handle a . wildcard? You must run a for loop over all 26 children and recursively search all non-null paths!
3. Word Search II (LeetCode 212 - Hard)
   • Goal: Combine DFS Backtracking with Trie Pruning.

8. Summary

• The Use Case: Blazing fast $O(L)$ prefix matching for massive string datasets.
• The Node: TrieNode[] children = new TrieNode[26]; boolean isWord;.
• The Mapping: The character is the index of the array (c - 'a'), not a stored value.
• Pruning: Combining a Trie with DFS (like in Word Search) is a FAANG-favorite optimization technique.