Trie

Use Cases for Trie Data Structures

Use Case	Description	Example
Autocomplete Suggestions	Provide real-time suggestions as users type in a search box.	Typing "app" in a search bar could suggest "apple," "application," and "appetizer."
Prefix Matching	Efficiently find all words in a dataset that start with a given prefix.	Given the prefix "pre," the Trie can return "prefix," "predecessor," and "presentation."
Data Compression	Implement algorithms like Lempel-Ziv (used in formats like ZIP) to store repeated patterns.	Use a Trie to store patterns of strings for efficient compression.

Code Template

Class initializing

Initializes an empty dictionary to hold child nodes for each character.
Sets a boolean flag to indicate if this node marks the end of a valid word.

Insert a new word

Starts at the root and iterates through each character in the word.
If a character is not already a child, it creates a new TrieNode for that character.

Internal search

_search_prefix(prefix) walks from the root through every character in prefix.
If a character is missing, return None. Otherwise, return the final TrieNode. Returning the node lets search and startsWith reuse the same helper.

Search by prefix or word

startsWith(prefix) only needs to know whether _search_prefix(prefix) found a node.
search(word) must also check node.is_end, because a prefix is not always a complete word.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

Common mistakes

Wrong Node Structure Implementation

# Wrong: incorrect children initialization
class TrieNode:
    def __init__(self):
        self.children = []  # Should be dictionary
        self.is_end = False
# Wrong: missing end marker
class TrieNode:
    def __init__(self):
        self.children = {}  # Missing is_end flag
# Correct:
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Wrong Insert Implementation

# Wrong: not updating node reference
def insert(self, word):
    node = self.root
    for char in word:
        if char not in self.root.children:  # Using root instead of current node
            self.root.children[char] = TrieNode()
# Wrong: forgetting end marker
def insert(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    # Missing node.is_end = True
# Correct:
def insert(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end = True

Wrong Search Implementation

# Wrong: incorrect return condition
def search(self, word):
    node = self._search_prefix(word)
    return node  # Should check is_end
# Wrong: not handling None return
def search(self, word):
    node = self._search_prefix(word)
    return node.is_end  # Could raise AttributeError
# Correct:
def search(self, word):
    node = self._search_prefix(word)
    return bool(node and node.is_end)

Issues and consideration

Concurrency: The current implementation is not thread-safe, which can lead to issues if multiple threads modify the Trie simultaneously. Implement locking mechanisms or use concurrent data structures if the Trie will be accessed or modified in a multi-threaded environment.
Balancing Trade-offs: The choice between a standard Trie and more advanced structures (like a suffix tree or a compressed Trie) can affect performance and complexity. Analyze the specific requirements of your application (e.g., search speed, memory efficiency) to choose the most appropriate data structure.

208. Implement Trie (Prefix Tree)

# This is the code template directly.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def _search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def startsWith(self, prefix):
        return bool(self._search_prefix(prefix))

    def search(self, word):
        node = self._search_prefix(word)
        return bool(node and node.is_end)

212. Word Search II

# Reuse the same Trie template to store all words.
# The problem-specific part is DFS on the board while following trie children.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def _search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def startsWith(self, prefix):
        return bool(self._search_prefix(prefix))

    def search(self, word):
        node = self._search_prefix(word)
        return bool(node and node.is_end)

class Solution:
    def findWords(self, board, words):
        trie = Trie()
        for word in words:
            trie.insert(word)

        m, n = len(board), len(board[0])
        result = set()
        visited = [[False] * n for _ in range(m)]

        def backtrack(x, y, node, path):
            if node.is_end:
                result.add(path)
                node.is_end = False

            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    char = board[nx][ny]
                    if char in node.children:
                        visited[nx][ny] = True
                        backtrack(nx, ny, node.children[char], path + char)
                        visited[nx][ny] = False

        for i in range(m):
            for j in range(n):
                char = board[i][j]
                if char in trie.root.children:
                    visited[i][j] = True
                    backtrack(i, j, trie.root.children[char], char)
                    visited[i][j] = False

        return list(result)

Resources

Trie Data Structure (EXPLAINED)

Trie

Use Cases for Trie Data Structures

Code Template

Class initializing

Insert a new word

Internal search

Search by prefix or word

Common mistakes

Issues and consideration

Related Problem

Resources