Tries (Prefix Trees) Made Easy

# Simple Trie Node class TrieNode: def __init__(self): self.children = {} # Dictionary to store child nodes self.is_end_word = False # Is this the end of a word? # The Trie itself class Trie: def __init__(self): self.root = TrieNode() # Start with empty root def insert(self, word): """Add a word to the Trie""" node = self.root # Travel down the tree, creating nodes as needed for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] # Mark the end of the word node.is_end_word = True print(f"✅ Added '{word}' to the Trie!") def search(self, word): """Check if a word exists in the Trie""" node = self.root for char in word: if char not in node.children: return False # Character not found node = node.children[char] return node.is_end_word # Must be a complete word # Try it out! trie = Trie() trie.insert("cat") trie.insert("car") print(trie.search("cat")) # True ✓ print(trie.search("ca")) # False (not a complete word)

def autocomplete(self, prefix): """Find all words that start with prefix""" results = [] node = self.root # Step 1: Navigate to the prefix end for char in prefix: if char not in node.children: return results # Prefix doesn't exist node = node.children[char] # Step 2: Find all words from this point def dfs(current_node, current_word): if current_node.is_end_word: results.append(current_word) for char, child_node in current_node.children.items(): dfs(child_node, current_word + char) # Include the prefix itself if it's a word if node.is_end_word: results.append(prefix) # Find all continuations for char, child_node in node.children.items(): dfs(child_node, prefix + char) return results # Example usage trie = Trie() words = ["apple", "app", "apricot", "application"] for word in words: trie.insert(word) suggestions = trie.autocomplete("app") print(suggestions) # ['app', 'apple', 'application']

def find_words_in_grid(board, word_list): """Find all words from word_list in the grid""" # Build Trie from word list trie = Trie() for word in word_list: trie.insert(word) rows, cols = len(board), len(board[0]) found_words = set() def dfs(i, j, node, path): # Check if we found a word if node.is_end_word: found_words.add(path) # Check bounds and if character exists in Trie if i < 0 or i >= rows or j < 0 or j >= cols: return char = board[i][j] if char not in node.children: return # Mark as visited and explore neighbors board[i][j] = '#' for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]: dfs(i + di, j + dj, node.children[char], path + char) # Restore the cell board[i][j] = char # Start DFS from each cell for i in range(rows): for j in range(cols): dfs(i, j, trie.root, "") return list(found_words)

def longest_common_prefix(self): """Find the longest prefix shared by all words""" node = self.root prefix = [] # Keep going while there's only one path while node and len(node.children) == 1 and not node.is_end_word: char = list(node.children.keys())[0] prefix.append(char) node = node.children[char] return ''.join(prefix) # Example trie = Trie() words = ["flower", "flow", "flight"] for word in words: trie.insert(word) print(trie.longest_common_prefix()) # "fl"

class CompressedTrieNode: def __init__(self): self.children = {} self.is_end_word = False self.edge_label = "" # Store edge string def compress_trie(root): """Compress chains of single children""" def compress_node(node): # If only one child and not end of word if len(node.children) == 1 and not node.is_end_word: child_char = list(node.children.keys())[0] child_node = node.children[child_char] # Merge with child node.edge_label += child_char node.children = child_node.children node.is_end_word = child_node.is_end_word # Continue compression compress_node(node) else: # Recursively compress children for child in node.children.values(): compress_node(child) compress_node(root) return root

def delete(self, word): """Delete a word from the Trie""" def delete_helper(node, word, index): if index == len(word): # Reached end of word if not node.is_end_word: return False # Word doesn't exist node.is_end_word = False # Return True if node has no children return len(node.children) == 0 char = word[index] if char not in node.children: return False should_delete = delete_helper(node.children[char], word, index + 1) if should_delete: del node.children[char] # Return True if current node has no children and is not end of another word return len(node.children) == 0 and not node.is_end_word return False delete_helper(self.root, word, 0)

def find_maximum_xor(nums): """Find maximum XOR of any two numbers""" class BitTrieNode: def __init__(self): self.children = {} # 0 or 1 root = BitTrieNode() # Insert all numbers into Trie for num in nums: node = root for i in range(31, -1, -1): bit = (num >> i) & 1 if bit not in node.children: node.children[bit] = BitTrieNode() node = node.children[bit] max_xor = 0 # Find maximum XOR for each number for num in nums: node = root current_xor = 0 for i in range(31, -1, -1): bit = (num >> i) & 1 # Try to go opposite direction for maximum XOR toggle_bit = 1 - bit if toggle_bit in node.children: current_xor |= (1 << i) node = node.children[toggle_bit] else: node = node.children[bit] max_xor = max(max_xor, current_xor) return max_xor