Prefix Tree (Tries)

Imagine building a dictionary for an autocomplete system. You need to store thousands of words in a way that allows for extremely fast prefix-based searches (e.g., finding all words that start with "pre"). A hash set could tell you if a word exists in $O(1)$, but it can't efficiently find all words with a given prefix. This is where a Trie shines.

Take some time to try this problem out:

Problem: Implement Trie (Prefix Tree) (LeetCode Link): Implement a trie with insert, search, and startsWith methods.

The Structure: A Tree of Characters

A Trie is made of nodes, where each node represents a character and contains two key pieces of information:

1. Children: A mapping from a character to a child TrieNode. This is often an array of size 26 for lowercase English letters or a hash map for a more flexible character set.
2. isEndOfWord Flag: A boolean that is true only if the path from the root to this node represents a complete word.

Walkthrough: Implementing a Trie

Let's build the Trie class step-by-step.

1. The TrieNode

First, we define the node structure.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

2. The Trie Class and its Methods

Now, we implement the main class.

insert(word)

To insert a word, we traverse from the root, creating nodes for characters as needed.

def insert(self, word: str) -> None:
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            node.children[c - 'a'] = new TrieNode();
        }
        node = node.children[c - 'a'];
    }
    node.isEndOfWord = true;
}

void insert(string word) {
    TrieNode* node = root;
    for (char c : word) {
        if (node->children[c - 'a'] == nullptr) {
            node->children[c - 'a'] = new TrieNode();
        }
        node = node->children[c - 'a'];
    }
    node->isEndOfWord = true;
}

search(word)

To search for a complete word, we traverse the path. The final node must exist and have its isEndOfWord flag set to true.

def search(self, word: str) -> bool:
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

public boolean search(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            return false;
        }
        node = node.children[c - 'a'];
    }
    return node.isEndOfWord;
}

bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
        if (node->children[c - 'a'] == nullptr) {
            return false;
        }
        node = node->children[c - 'a'];
    }
    return node->isEndOfWord;
}

startsWith(prefix)

To search for a prefix, we just need to ensure the path exists. We don't care about the isEndOfWord flag. This is what makes Tries so fast for autocomplete.

def startsWith(self, prefix: str) -> bool:
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True

public boolean startsWith(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            return false;
        }
        node = node.children[c - 'a'];
    }
    return true;
}

bool startsWith(string prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        if (node->children[c - 'a'] == nullptr) {
            return false;
        }
        node = node->children[c - 'a'];
    }
    return true;
}

More Problems & Variations

1. Design Add and Search Words Data Structure (LeetCode Link): A variation where the search method can contain a . character, which matches any single letter. 💡 HintYou'll need to modify your search function to be recursive. When you encounter a ., you must iterate through all non-null children of the current node and recursively search down each of those paths.

Bonus Points: Tries + Backtracking

The true power of Tries is unlocked when you combine them with other algorithms, especially backtracking on a grid.

Problem: Word Search II (LeetCode Link): You are given a grid of characters and a list of words. Find all words from the list that can be formed in the grid.

A naive approach of backtracking for every single word in the dictionary would be too slow. The optimal solution is to:

1. Build a Trie: Insert all the words from the dictionary into a single Trie.
2. Backtrack on the Grid: Perform a backtracking search (DFS) starting from every cell in the grid.
3. Prune with the Trie: As you build a path during your backtracking (e.g., "c" -> "ca" -> "cat"), check if the current path exists as a prefix in the Trie. If it doesn't (e.g., there are no words starting with "cax"), you can immediately stop exploring that path and backtrack. This prunes the search space massively. If your path corresponds to a node with isEndOfWord = true, you've found a word.