TrieNode A trie node implementation representing a single node in the trie structure.
Constructor Create a new trie node with an empty children dictionary.
Example: from ucx_dsa import TrieNode node = TrieNode()
Attributes A dictionary mapping characters to child TrieNode references. Keys are characters, values are TrieNode instances.
Trie A trie (prefix tree) implementation for efficient string storage and retrieval.
Constructor Initialize an empty trie with a root node.
Example: from ucx_dsa import Trie trie = Trie()
Attributes The root node of the trie.
Class-level constant used to mark the end of a word. Default is ”*”.
Methods insert(word) Insert a word into the trie.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "hello" ) trie.insert( "help" ) trie.insert( "world" )
Time Complexity: O(m) where m is the length of the wordsearch(word) Search for a complete word in the trie.
True if the complete word is found, False otherwise.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "hello" ) trie.insert( "help" ) print (trie.search( "hello" )) # Output: True print (trie.search( "hel" )) # Output: False (prefix only) print (trie.search( "world" )) # Output: False (not inserted)
Time Complexity: O(m) where m is the length of the wordsearch_node(substr) Search for a substring in the trie and return the node where it ends.
A substring to search for.
The TrieNode where the substring ends, or None if not found.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "hello" ) node = trie.search_node( "hel" ) if node: print ( "Substring found" ) # Output: Substring found
Time Complexity: O(m) where m is the length of the substringdelete(word, i=0, current=None) Delete a word from the trie.
trie.delete(word, i = 0 , current = None )
The index of the character (used internally for recursion).
The current node (used internally for recursion).
True if the child node can be deleted, False otherwise.
Raises:
ValueError: If the word is not found
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "hello" ) trie.insert( "help" ) print (trie.search( "hello" )) # Output: True trie.delete( "hello" ) print (trie.search( "hello" )) # Output: False print (trie.search( "help" )) # Output: True (still exists)
Time Complexity: O(m) where m is the length of the wordlist_words() Return a list of all words in the trie.
A list of all words stored in the trie, in alphabetical order.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "cat" ) trie.insert( "car" ) trie.insert( "card" ) trie.insert( "dog" ) print (trie.list_words()) # Output: ['car', 'card', 'cat', 'dog']
Time Complexity: O(n) where n is the total number of characters in all wordsbuild_word_list(node=None, word="", words=None) Helper method to build a list of words given a starting node.
trie.build_word_list( node = None , word = "" , words = None )
The current trie node. If None, uses the root.
The word being built during recursion.
The list of words being accumulated.
List of words starting from the given node.
Time Complexity: O(n) where n is the number of characters in the subtrieprefix(prefix) Return a list of words that begin with a given prefix.
The prefix to search for.
List of words that begin with the given prefix, or None if no matches found.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "apple" ) trie.insert( "application" ) trie.insert( "apply" ) trie.insert( "banana" ) print (trie.prefix( "app" )) # Output: ['apple', 'application', 'apply'] print (trie.prefix( "ban" )) # Output: ['banana'] print (trie.prefix( "xyz" )) # Output: None
Time Complexity: O(p + n) where p is the prefix length and n is the number of matching wordssuggest(prefix) Return a list of words similar to a given prefix using a fallback strategy.
The prefix to search for.
List of words that match the prefix. If no exact match, progressively removes characters from the end until matches are found, or None if empty prefix.
Example: from ucx_dsa import Trie trie = Trie() trie.insert( "hello" ) trie.insert( "help" ) trie.insert( "helicopter" ) print (trie.suggest( "helx" )) # Output: ['hello', 'helicopter', 'help'] (falls back to "hel") print (trie.suggest( "hello" )) # Output: ['hello'] print (trie.suggest( "xyz" )) # Returns words starting with "xy", "x", or None
Time Complexity: O(p * (p + n)) worst case, where p is prefix lengthcopy_node(node) Recursively create a deep copy of a node and its children.
A deep copy of the node and all its descendants.
Time Complexity: O(n) where n is the number of nodes in the subtriecopy() Create a deep copy of the entire trie.
A new Trie instance with the same structure and words.
Example: from ucx_dsa import Trie original = Trie() original.insert( "hello" ) original.insert( "world" ) copy = original.copy() copy.insert( "test" ) print (original.list_words()) # Output: ['hello', 'world'] print (copy.list_words()) # Output: ['hello', 'test', 'world']
Time Complexity: O(n) where n is the total number of charactersSpecial Methods __eq__(other) Compare two Trie objects for value-based equality based on their word sets.
The other trie to compare against.
True if both are Trie instances and contain the same set of words.
Example: from ucx_dsa import Trie trie1 = Trie() trie1.insert( "hello" ) trie1.insert( "world" ) trie2 = Trie() trie2.insert( "world" ) trie2.insert( "hello" ) print (trie1 == trie2) # Output: True (same words, order doesn't matter)
Time Complexity: O(n) where n is the total number of charactersUsage Examples Autocomplete System from ucx_dsa import Trie class Autocomplete : def __init__ ( self ): self .trie = Trie() def add_word ( self , word ): self .trie.insert(word.lower()) def get_suggestions ( self , prefix ): return self .trie.prefix(prefix.lower()) autocomplete = Autocomplete() autocomplete.add_word( "python" ) autocomplete.add_word( "programming" ) autocomplete.add_word( "program" ) autocomplete.add_word( "progress" ) autocomplete.add_word( "java" ) print (autocomplete.get_suggestions( "pro" )) # Output: ['program', 'programming', 'progress']
Spell Checker from ucx_dsa import Trie class SpellChecker : def __init__ ( self , dictionary ): self .trie = Trie() for word in dictionary: self .trie.insert(word.lower()) def is_valid ( self , word ): return self .trie.search(word.lower()) def suggest_corrections ( self , word ): return self .trie.suggest(word.lower()) dictionary = [ "hello" , "world" , "help" , "heap" , "tree" ] spell_checker = SpellChecker(dictionary) print (spell_checker.is_valid( "hello" )) # Output: True print (spell_checker.is_valid( "helo" )) # Output: False print (spell_checker.suggest_corrections( "helo" )) # Output: ['hello', 'help', 'heap']
Word Game Dictionary from ucx_dsa import Trie class WordGame : def __init__ ( self ): self .trie = Trie() self .used_words = set () def add_valid_word ( self , word ): self .trie.insert(word) def is_valid_move ( self , word ): return self .trie.search(word) and word not in self .used_words def mark_used ( self , word ): if self .is_valid_move(word): self .used_words.add(word) return True return False game = WordGame() game.add_valid_word( "cat" ) game.add_valid_word( "dog" ) game.add_valid_word( "catch" ) print (game.is_valid_move( "cat" )) # Output: True print (game.mark_used( "cat" )) # Output: True print (game.is_valid_move( "cat" )) # Output: False (already used)
IP Routing Table from ucx_dsa import Trie class IPRouter : def __init__ ( self ): self .trie = Trie() def add_route ( self , ip_prefix ): self .trie.insert(ip_prefix) def find_routes ( self , prefix ): return self .trie.prefix(prefix) router = IPRouter() router.add_route( "192.168.1.1" ) router.add_route( "192.168.1.2" ) router.add_route( "192.168.2.1" ) router.add_route( "10.0.0.1" ) print (router.find_routes( "192.168.1" )) # Output: ['192.168.1.1', '192.168.1.2']
Notes
Trie Performance Characteristics