Trie Operations
Traverse
100%
Ctrl + scroll to zoom
Words 2 · Nodes 5 · Word length 2–3
Trie
Insert and search strings in a trie - see how prefixes share paths in the tree.
Time O(k) · Space O(n·k)
Implementation
from enum import Enum
class TrieNode:
"""A single node in the trie."""
__slots__ = ("children", "end_of_word", "char")
def __init__(self, char: str = ""):
"""Initialize a trie node with a character."""
self.char = char # Character stored at this node (empty for root)
self.children: dict[str, "TrieNode"] = {} # Map from char to child node
self.end_of_word: bool = False # True if this node marks end of a word
def __str__(self):
return f"TrieNode('{self.char}', end={self.end_of_word})"
def __repr__(self):
return self.__str__()
class Trie:
"""
Trie (Prefix Tree) implementation.
Provides operations for inserting, searching, and deleting strings,
as well as prefix matching and traversal methods.
"""
def __init__(self):
"""Initialize an empty trie with a root node."""
self.root = TrieNode() # Root has empty character
def __contains__(self, word: str) -> bool:
"""Allow 'word in trie' syntax."""
return self.search(word)
# -------------------------------------------------------------------------
# Core Operations
# -------------------------------------------------------------------------
def insert(self, word: str) -> None:
"""
Insert a word into the trie.
Creates new nodes as needed along the path.
"""
if not word:
return
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode(char)
node = node.children[char]
node.end_of_word = True
def search(self, word: str) -> bool:
"""
Search for a complete word in the trie.
Returns True if the word exists, False otherwise.
"""
node = self._find_node(word)
return node is not None and node.end_of_word
def delete(self, word: str) -> bool:
"""
Delete a word from the trie.
Returns True if deletion was successful, False if word not found.
Handles three cases:
1. Word not found - return False
2. Word is prefix of another word - only unmark end_of_word
3. Word has unique suffix - remove nodes that are not part of other words
"""
if not word:
return False
def _delete_recursive(node: TrieNode, word: str, depth: int) -> bool:
"""
Recursively delete word from trie.
Returns True if current node should be deleted (has no children and not end of word).
"""
if depth == len(word):
# Reached end of word
if not node.end_of_word:
return False # Word doesn't exist
node.end_of_word = False
# Delete node if it has no children
return len(node.children) == 0
char = word[depth]
if char not in node.children:
return False # Word doesn't exist
child = node.children[char]
should_delete_child = _delete_recursive(child, word, depth + 1)
if should_delete_child:
del node.children[char]
# Current node can be deleted if it's not end of word and has no children
return not node.end_of_word and len(node.children) == 0
return False
# Start deletion from root
_delete_recursive(self.root, word, 0)
return True
def starts_with(self, prefix: str) -> bool:
"""
Check if any word in the trie starts with the given prefix.
Returns True if prefix exists, False otherwise.
"""
return self._find_node(prefix) is not None
def _find_node(self, prefix: str) -> TrieNode | None:
"""
Find the node corresponding to the last character of prefix.
Returns None if prefix doesn't exist in trie.
"""
if prefix == "":
return self.root
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
# -------------------------------------------------------------------------
# Word Retrieval Methods
# -------------------------------------------------------------------------
def get_all_words(self) -> list[str]:
"""
Get all complete words stored in the trie.
Returns a list of all words in lexicographical order.
"""
words = []
self._collect_words(self.root, "", words)
return words
def get_words_with_prefix(self, prefix: str) -> list[str]:
"""
Get all words that start with the given prefix.
Returns empty list if prefix doesn't exist.
"""
node = self._find_node(prefix)
if node is None:
return []
words = []
self._collect_words(node, prefix, words)
return words
def _collect_words(self, node: TrieNode, prefix: str, words: list[str]) -> None:
"""Recursively collect all words starting from node with given prefix."""
if node.end_of_word:
words.append(prefix)
# Process children in sorted order for consistent output
for char in sorted(node.children.keys()):
self._collect_words(node.children[char], prefix + char, words)
# -------------------------------------------------------------------------
# Traversal Methods
# -------------------------------------------------------------------------
class TraverseOrder(Enum):
"""Enumeration of trie traversal orders."""
preorder = 1 # Visit node, then children (depth-first)
postorder = 2 # Visit children, then node (depth-first)
levelorder = 3 # Breadth-first traversal
def traverse(self, order: TraverseOrder) -> list[str]:
"""
Traverse the trie in the specified order.
Returns a list of characters visited (including empty root marker).
"""
result = []
def _preorder(node: TrieNode):
result.append(node.char if node.char else "[root]")
for char in sorted(node.children.keys()):
_preorder(node.children[char])
def _postorder(node: TrieNode):
for char in sorted(node.children.keys()):
_postorder(node.children[char])
result.append(node.char if node.char else "[root]")
def _levelorder():
if not self.root.children:
result.append("[root]")
return
queue = [self.root]
while queue:
node = queue.pop(0)
result.append(node.char if node.char else "[root]")
for char in sorted(node.children.keys()):
queue.append(node.children[char])
traversals = {
Trie.TraverseOrder.preorder: _preorder,
Trie.TraverseOrder.postorder: _postorder,
Trie.TraverseOrder.levelorder: _levelorder,
}
if order not in traversals:
raise TypeError("Invalid traverse order passed.")
if order == Trie.TraverseOrder.levelorder:
traversals[order]()
else:
traversals[order](self.root)
return result
# -------------------------------------------------------------------------
# Utility Methods
# -------------------------------------------------------------------------
def count_words(self) -> int:
"""Return the total number of complete words in the trie."""
return len(self.get_all_words())
def count_nodes(self) -> int:
"""Return the total number of nodes in the trie (including root)."""
count = 0
def _count(node: TrieNode):
nonlocal count
count += 1
for child in node.children.values():
_count(child)
_count(self.root)
return count
def is_empty(self) -> bool:
"""Return True if the trie contains no words."""
return len(self.root.children) == 0
def longest_common_prefix(self) -> str:
"""
Find the longest common prefix of all words in the trie.
Returns empty string if no common prefix or trie is empty.
"""
if self.is_empty():
return ""
prefix = []
node = self.root
while len(node.children) == 1 and not node.end_of_word:
char = next(iter(node.children.keys()))
prefix.append(char)
node = node.children[char]
return "".join(prefix)
def levels_traversal(self) -> dict[int, list[str]]:
"""Return characters grouped by level (breadth-first). Level 0 is root."""
levels: dict[int, list[str]] = {}
queue = [(self.root, 0)]
for node, level in queue:
if level not in levels:
levels[level] = []
levels[level].append(node.char if node.char else "[root]")
for char in sorted(node.children.keys()):
queue.append((node.children[char], level + 1))
return levels
def min_depth(self) -> int:
"""Return minimum depth (shortest word length). -1 if empty."""
if self.is_empty():
return -1
min_lvl = -1
def _dfs(node: TrieNode, depth: int):
nonlocal min_lvl
if node.end_of_word:
if min_lvl == -1 or depth < min_lvl:
min_lvl = depth
for child in node.children.values():
_dfs(child, depth + 1)
_dfs(self.root, 0)
return min_lvl
def max_depth(self) -> int:
"""Return maximum depth (longest word length). -1 if empty."""
if self.is_empty():
return -1
max_lvl = 0
def _dfs(node: TrieNode, depth: int):
nonlocal max_lvl
if node.end_of_word and depth > max_lvl:
max_lvl = depth
for child in node.children.values():
_dfs(child, depth + 1)
_dfs(self.root, 0)
return max_lvl
# Example usage:
if __name__ == "__main__":
trie = Trie()
# Insert words
words = ["apple", "app", "application", "apply", "banana", "band", "bandana"]
for word in words:
trie.insert(word)
# Search
print("Search 'apple':", trie.search("apple")) # True
print("Search 'app':", trie.search("app")) # True
print("Search 'appl':", trie.search("appl")) # False (not a complete word)
print("'banana' in trie:", "banana" in trie) # True
# Prefix matching
print("Starts with 'app':", trie.starts_with("app")) # True
print("Starts with 'xyz':", trie.starts_with("xyz")) # False
print("Words with prefix 'app':", trie.get_words_with_prefix("app"))
# ['app', 'apple', 'application', 'apply']
# Get all words
print("All words:", trie.get_all_words())
# ['app', 'apple', 'application', 'apply', 'banana', 'band', 'bandana']
# Statistics
print("Word count:", trie.count_words()) # 7
print("Node count:", trie.count_nodes())
# Traversals
print("Preorder:", trie.traverse(Trie.TraverseOrder.preorder))
print("Levelorder:", trie.traverse(Trie.TraverseOrder.levelorder))
print("By levels:", trie.levels_traversal())
# Delete
trie.delete("app")
print("After deleting 'app':", trie.get_all_words())
print("Search 'app' after delete:", trie.search("app")) # False
print("Search 'apple' after delete:", trie.search("apple")) # True (still exists)
# Longest common prefix
trie2 = Trie()
for word in ["flower", "flow", "flight"]:
trie2.insert(word)
print("Longest common prefix:", trie2.longest_common_prefix()) # "fl"
About Trie
How Trie Works
A trie (prefix tree) is a tree-like data structure that stores strings character by character. Each node represents a character, and paths from root to marked nodes represent stored strings. Tries enable O(k) lookup where k is the string length, regardless of how many strings are stored.
To insert a string, traverse from the root creating child nodes for each character that doesn't exist. Mark the final node as an end-of-word. To search, follow the character path from the root - if you reach the end and the node is marked, the string exists.
Complexity
- Time
- O(k)
- Space
- O(n·k)
When to Use Trie
- Autocomplete and type-ahead suggestions
- Spell checking and dictionary lookups
- IP routing tables and prefix matching