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

Implement an internal method checks if a given prefix exists in the Trie.

Search by prefix or word

Use _search_prefix function to check if given prefix or word exists in the Trie.

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 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)

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 False
            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 node and node.is_end

212. Word Search II

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 False
            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 node and node.is_end

class Solution:
    def findWords(self, board, words):
        # Initialize the Trie and insert all 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:  # If we reached the end of a word
                result.add(path)  # Add the word to the result
                node.is_end = False  # Avoid adding the same word again

            # Explore the adjacent cells
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # Up, Down, Left, Right
                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:  # If the character is in the Trie
                        visited[nx][ny] = True  # Mark the cell as visited
                        backtrack(nx, ny, node.children[char], path + char)  # Recur for the next cell
                        visited[nx][ny] = False  # Backtrack: unmark the cell

        for i in range(m):
            for j in range(n):
                char = board[i][j]
                if char in trie.root.children:  # Start backtracking if the character is in the Trie
                    visited[i][j] = True  # Mark the cell as visited
                    backtrack(i, j, trie.root.children[char], char)  # Start backtracking
                    visited[i][j] = False  # Backtrack: unmark the cell

        return list(result)  # Convert the result set to a list

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