Trie (Prefix Tree)

A trie (also called prefix tree) is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It's particularly efficient for operations involving prefixes, such as autocomplete functionality, spell checkers, and IP routing tables.

Features

Efficient string storage - shared prefixes reduce memory usage
Fast prefix operations - check if any word starts with a prefix
Autocomplete functionality - get suggestions for partial words
Word management - insert, search, and delete words efficiently
Case sensitivity control - support both case-sensitive and case-insensitive modes
Advanced operations - longest common prefix, shortest unique prefix
Memory efficient - common prefixes are stored only once
Flexible traversal - get all words or words with specific prefix

Time Complexities

Operation	Time Complexity	Description
Insert	O(m)	Insert word of length m
Search	O(m)	Search for word of length m
Delete	O(m)	Delete word of length m
Prefix Check	O(p)	Check if prefix of length p exists
Get Words with Prefix	O(p + n·k)	p = prefix length, n = results, k = avg word length
Autocomplete	O(p + n·k)	Get suggestions for prefix
Longest Common Prefix	O(n·m)	n = number of words, m = avg length
Count with Prefix	O(p + n·k)	Count words starting with prefix

Space Complexity: O(ALPHABET_SIZE × N × M) where N is number of words and M is average length

Basic Usage

Creating and Initializing

from algo.data_structs.strings.trie import Trie, TrieNode

# Create empty trie (case-sensitive by default)
trie = Trie()
print(trie.is_empty())         # True
print(trie.size())             # 0
print(len(trie))               # 0
print(trie.case_sensitive)     # True

# Create case-insensitive trie
trie_ci = Trie(case_sensitive=False)
print(trie_ci.case_sensitive)  # False

# Check initial state
print(str(trie))               # Empty Trie
print(repr(trie))              # Trie(size=0, case_sensitive=True)

Creating Nodes

# Create individual trie nodes
root = TrieNode()
print(root.char)               # None (root has no character)
print(root.is_end)             # False
print(root.has_children())     # False

# Create character node
node = TrieNode('a', is_end=True)
print(node.char)               # 'a'
print(node.is_end)             # True
print(str(node))               # TrieNode('a', end=True)

# Add children to node
child_b = node.add_child('b')
child_c = node.add_child('c')
print(node.has_children())     # True
print(node.get_children_chars()) # ['b', 'c']

Basic Word Operations

# Insert words
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("card")

print(trie.size())             # 3
print(trie.is_empty())         # False
print(len(trie))               # 3

# Search for words
print(trie.search("cat"))      # True
print(trie.search("car"))      # True
print(trie.search("ca"))       # False (not a complete word)
print(trie.search("cards"))    # False

# Using 'in' operator
print("cat" in trie)           # True
print("dog" in trie)           # False

Word Insertion

Single Word Insertion

trie = Trie()

# Insert first word
trie.insert("hello")
print(f"Size: {trie.size()}")  # Size: 1
print(f"Contains 'hello': {trie.search('hello')}")  # True
print(f"Contains 'hell': {trie.search('hell')}")    # False

# Insert related word
trie.insert("help")
print(f"Size: {trie.size()}")  # Size: 2
print(f"Words: {trie.get_all_words()}")  # ['hello', 'help']

Multiple Word Insertion

trie = Trie()
words = ["apple", "app", "application", "apply", "appreciate"]

# Insert all words
for word in words:
    trie.insert(word)

print(f"Total words: {trie.size()}")  # Total words: 5

# Verify all words were inserted
for word in words:
    assert trie.search(word), f"Word '{word}' not found"

print("All words successfully inserted!")

Handling Duplicates

trie = Trie()

# Insert same word multiple times
trie.insert("test")
print(f"Size after first insert: {trie.size()}")  # 1

trie.insert("test")  # Duplicate - should not increase size
print(f"Size after duplicate: {trie.size()}")     # 1

trie.insert("testing")  # Different word
print(f"Size after new word: {trie.size()}")      # 2

Prefix Relationships

trie = Trie()

# Insert words where one is prefix of another
trie.insert("car")
trie.insert("card")
trie.insert("cards")
trie.insert("care")
trie.insert("careful")

print(f"All words: {trie.get_all_words()}")
# ['car', 'card', 'cards', 'care', 'careful']

# All are separate words even though some are prefixes
print(f"'car' exists: {trie.search('car')}")     # True
print(f"'card' exists: {trie.search('card')}")   # True
print(f"'care' exists: {trie.search('care')}")   # True

Case Sensitivity

Case-Sensitive Mode (Default)

# Case-sensitive trie treats different cases as different words
trie_cs = Trie(case_sensitive=True)
trie_cs.insert("Hello")
trie_cs.insert("hello")
trie_cs.insert("HELLO")

print(f"Size: {trie_cs.size()}")           # 3 (all different)
print(f"'Hello': {trie_cs.search('Hello')}")  # True
print(f"'hello': {trie_cs.search('hello')}")  # True
print(f"'HELLO': {trie_cs.search('HELLO')}")  # True
print(f"'hElLo': {trie_cs.search('hElLo')}")  # False

Case-Insensitive Mode

# Case-insensitive trie normalizes to lowercase
trie_ci = Trie(case_sensitive=False)
trie_ci.insert("Hello")
trie_ci.insert("hello")
trie_ci.insert("HELLO")
trie_ci.insert("hElLo")

print(f"Size: {trie_ci.size()}")           # 1 (all same word)
print(f"'Hello': {trie_ci.search('Hello')}")  # True
print(f"'hello': {trie_ci.search('hello')}")  # True
print(f"'HELLO': {trie_ci.search('HELLO')}")  # True
print(f"'hElLo': {trie_ci.search('hElLo')}")  # True

Handling Empty Strings

trie = Trie()

# Empty strings are ignored
trie.insert("")
print(f"Size after empty insert: {trie.size()}")  # 0
print(f"Empty string search: {trie.search('')}")  # False

# Insert valid word
trie.insert("word")
print(f"Size after valid insert: {trie.size()}")  # 1

Prefix Operations

Checking Prefixes

trie = Trie()
words = ["cat", "car", "card", "care", "dog", "door", "dodge"]
for word in words:
    trie.insert(word)

# Check if any word starts with prefix
print(f"Starts with 'ca': {trie.starts_with('ca')}")    # True
print(f"Starts with 'car': {trie.starts_with('car')}")  # True
print(f"Starts with 'do': {trie.starts_with('do')}")    # True
print(f"Starts with 'bat': {trie.starts_with('bat')}")  # False

# Empty prefix check
print(f"Starts with '': {trie.starts_with('')}")        # True (if trie not empty)

Getting Words with Prefix

# Get all words that start with a specific prefix
car_words = trie.get_words_with_prefix("car")
print(f"Words starting with 'car': {car_words}")
# ['car', 'card', 'care']

do_words = trie.get_words_with_prefix("do")
print(f"Words starting with 'do': {do_words}")
# ['dog', 'dodge', 'door']

# Non-existent prefix
xyz_words = trie.get_words_with_prefix("xyz")
print(f"Words starting with 'xyz': {xyz_words}")
# []

# Single character prefix
c_words = trie.get_words_with_prefix("c")
print(f"Words starting with 'c': {c_words}")
# ['car', 'card', 'care', 'cat']

Counting Words with Prefix

# Count words without retrieving them
print(f"Count 'car' prefix: {trie.count_words_with_prefix('car')}")  # 3
print(f"Count 'ca' prefix: {trie.count_words_with_prefix('ca')}")    # 4
print(f"Count 'do' prefix: {trie.count_words_with_prefix('do')}")    # 3
print(f"Count 'z' prefix: {trie.count_words_with_prefix('z')}")      # 0

# More efficient than len(get_words_with_prefix()) for large results

Getting All Words

# Retrieve all words in the trie
all_words = trie.get_all_words()
print(f"All words: {all_words}")
# ['car', 'card', 'care', 'cat', 'dog', 'dodge', 'door']

# Words are returned in alphabetical order
print(f"Total count: {len(all_words)}")  # 7
print(f"Same as size: {len(all_words) == trie.size()}")  # True

Autocomplete Functionality

Basic Autocomplete

trie = Trie()
dictionary = [
    "apple", "application", "apply", "appreciate", "approach",
    "banana", "band", "bandana", "bank",
    "cat", "car", "card", "care", "careful"
]

for word in dictionary:
    trie.insert(word)

# Get autocomplete suggestions
suggestions = trie.autocomplete("app")
print(f"Suggestions for 'app': {suggestions}")
# ['apple', 'application', 'apply', 'appreciate', 'approach']

suggestions = trie.autocomplete("ban")
print(f"Suggestions for 'ban': {suggestions}")
# ['banana', 'band', 'bandana', 'bank']

Limited Autocomplete

# Limit number of suggestions
limited_suggestions = trie.autocomplete("app", max_suggestions=3)
print(f"Limited suggestions for 'app': {limited_suggestions}")
# ['apple', 'application', 'apply']

# Very restrictive limit
single_suggestion = trie.autocomplete("car", max_suggestions=1)
print(f"Single suggestion for 'car': {single_suggestion}")
# ['car']

# No suggestions for non-existent prefix
no_suggestions = trie.autocomplete("xyz", max_suggestions=5)
print(f"Suggestions for 'xyz': {no_suggestions}")
# []

Real-world Autocomplete Example

def build_search_autocomplete():
    """Build a search autocomplete system."""
    search_trie = Trie(case_sensitive=False)

    # Common search terms
    search_terms = [
        "python programming", "python tutorial", "python basics",
        "java programming", "java tutorial", "java basics",
        "machine learning", "machine learning basics", "machine learning tutorial",
        "data science", "data structures", "data analysis",
        "web development", "web design", "website creation"
    ]

    # Build the trie
    for term in search_terms:
        search_trie.insert(term)

    return search_trie

# Use the autocomplete system
search_engine = build_search_autocomplete()

def get_search_suggestions(query, max_results=5):
    """Get search suggestions for a query."""
    return search_engine.autocomplete(query.lower(), max_results)

# Test the search system
print("Search suggestions for 'python':")
for suggestion in get_search_suggestions("python"):
    print(f"  - {suggestion}")

print("\nSearch suggestions for 'machine':")
for suggestion in get_search_suggestions("machine", 3):
    print(f"  - {suggestion}")

Word Deletion

Basic Deletion

trie = Trie()
words = ["cat", "car", "card", "care", "dog"]
for word in words:
    trie.insert(word)

print(f"Initial size: {trie.size()}")  # 5

# Delete existing word
success = trie.delete("card")
print(f"Deleted 'card': {success}")    # True
print(f"Size after deletion: {trie.size()}")  # 4
print(f"'card' exists: {trie.search('card')}")  # False
print(f"'car' exists: {trie.search('car')}")    # True (not affected)

Deleting Prefix Words

# When deleting a word that is prefix of others
trie = Trie()
trie.insert("car")
trie.insert("card")
trie.insert("cards")

print(f"Before deletion: {trie.get_all_words()}")  # ['car', 'card', 'cards']

# Delete the prefix word
trie.delete("car")
print(f"After deleting 'car': {trie.get_all_words()}")  # ['card', 'cards']
print(f"'car' exists: {trie.search('car')}")      # False
print(f"'card' exists: {trie.search('card')}")    # True
print(f"'cards' exists: {trie.search('cards')}")  # True

Deleting Non-existent Words

trie = Trie()
trie.insert("hello")

# Try to delete words that don't exist
print(f"Delete 'world': {trie.delete('world')}")   # False
print(f"Delete 'hell': {trie.delete('hell')}")     # False (prefix, not word)
print(f"Delete 'hellos': {trie.delete('hellos')}")  # False

# Size remains unchanged
print(f"Size: {trie.size()}")  # 1
print(f"'hello' still exists: {trie.search('hello')}")  # True

Deleting Last Word

trie = Trie()
trie.insert("onlyword")

print(f"Before deletion - Empty: {trie.is_empty()}")  # False

# Delete the only word
success = trie.delete("onlyword")
print(f"Deletion successful: {success}")    # True
print(f"After deletion - Empty: {trie.is_empty()}")  # True
print(f"Size: {trie.size()}")               # 0

Advanced Operations

Longest Common Prefix

# Find longest common prefix of all words
trie1 = Trie()
words1 = ["flower", "flow", "flight"]
for word in words1:
    trie1.insert(word)

lcp1 = trie1.get_longest_common_prefix()
print(f"LCP of {words1}: '{lcp1}'")  # 'fl'

# Trie with no common prefix
trie2 = Trie()
words2 = ["dog", "racecar", "car"]
for word in words2:
    trie2.insert(word)

lcp2 = trie2.get_longest_common_prefix()
print(f"LCP of {words2}: '{lcp2}'")  # ''

# Single word trie
trie3 = Trie()
trie3.insert("hello")
lcp3 = trie3.get_longest_common_prefix()
print(f"LCP of single word: '{lcp3}'")  # 'hello'

# Empty trie
trie4 = Trie()
lcp4 = trie4.get_longest_common_prefix()
print(f"LCP of empty trie: '{lcp4}'")  # ''

Shortest Unique Prefix

trie = Trie()
words = ["cat", "car", "card", "care", "dog", "door"]
for word in words:
    trie.insert(word)

# Find shortest unique prefix for each word
for word in words:
    prefix = trie.get_shortest_unique_prefix(word)
    print(f"Shortest unique prefix of '{word}': '{prefix}'")

# Output:
# Shortest unique prefix of 'cat': 'cat'
# Shortest unique prefix of 'car': 'car'  
# Shortest unique prefix of 'card': 'card'
# Shortest unique prefix of 'care': 'care'
# Shortest unique prefix of 'dog': 'd'
# Shortest unique prefix of 'door': 'do'

# Non-existent word
prefix = trie.get_shortest_unique_prefix("elephant")
print(f"Prefix for non-existent word: {prefix}")  # None

Contains Prefix Check

trie = Trie()
trie.insert("car")
trie.insert("card")
trie.insert("care")

# Check if trie contains any prefix of given words
print(f"Contains prefix of 'careful': {trie.contains_prefix('careful')}")  # True ('care')
print(f"Contains prefix of 'cards': {trie.contains_prefix('cards')}")      # True ('card')
print(f"Contains prefix of 'car': {trie.contains_prefix('car')}")          # True (exact match)
print(f"Contains prefix of 'cat': {trie.contains_prefix('cat')}")          # False
print(f"Contains prefix of 'dog': {trie.contains_prefix('dog')}")          # False

Iteration and Traversal

Iterating Over Words

trie = Trie()
words = ["apple", "banana", "cherry", "date"]
for word in words:
    trie.insert(word)

# Direct iteration
print("Words in trie:")
for word in trie:
    print(f"  - {word}")

# Using list comprehension
word_lengths = [len(word) for word in trie]
print(f"Word lengths: {word_lengths}")

# Convert to list
all_words = list(trie)
print(f"All words: {all_words}")

Using Built-in Functions

# len() function
print(f"Number of words: {len(trie)}")

# 'in' operator for membership testing
test_words = ["apple", "grape", "banana", "kiwi"]
for word in test_words:
    if word in trie:
        print(f"'{word}' is in the trie")
    else:
        print(f"'{word}' is NOT in the trie")

# bool() function (True if not empty)
print(f"Trie is not empty: {bool(trie)}")

empty_trie = Trie()
print(f"Empty trie is empty: {not bool(empty_trie)}")

String Representation and Debugging

String Representations

# Empty trie
empty_trie = Trie()
print(f"Empty trie: {str(empty_trie)}")     # Empty Trie
print(f"Empty repr: {repr(empty_trie)}")    # Trie(size=0, case_sensitive=True)

# Trie with few words
small_trie = Trie()
small_trie.insert("cat")
small_trie.insert("car")
print(f"Small trie: {str(small_trie)}")     # Trie(2 words): ['car', 'cat']

# Trie with many words (truncated display)
large_trie = Trie()
words = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"]
for word in words:
    large_trie.insert(word)
print(f"Large trie: {str(large_trie)}")     # Trie(7 words): ['apple', 'banana', 'cherry', 'date', 'elderberry']...

# Detailed representation
print(f"Detailed repr: {repr(large_trie)}")  # Trie(size=7, case_sensitive=True)

Node Representations

# Individual node representations
root = TrieNode()
print(f"Root node: {str(root)}")           # TrieNode('None', end=False)
print(f"Root repr: {repr(root)}")          # TrieNode(char='None', is_end=False, children=[])

char_node = TrieNode('a', is_end=True)
char_node.add_child('b')
char_node.add_child('c')
print(f"Char node: {str(char_node)}")      # TrieNode('a', end=True)
print(f"Char repr: {repr(char_node)}")     # TrieNode(char='a', is_end=True, children=['b', 'c'])

Error Handling and Edge Cases

Empty Trie Operations

empty_trie = Trie()

# Safe operations on empty trie
print(f"Empty trie size: {empty_trie.size()}")                    # 0
print(f"Empty trie is empty: {empty_trie.is_empty()}")            # True
print(f"Search in empty: {empty_trie.search('anything')}")        # False
print(f"Starts with in empty: {empty_trie.starts_with('any')}")   # False
print(f"Delete from empty: {empty_trie.delete('anything')}")      # False
print(f"Get all words: {empty_trie.get_all_words()}")             # []
print(f"Words with prefix: {empty_trie.get_words_with_prefix('a')}")  # []
print(f"Autocomplete: {empty_trie.autocomplete('a')}")            # []
print(f"LCP: '{empty_trie.get_longest_common_prefix()}'")         # ''

Special Characters and Unicode

# Trie with special characters
special_trie = Trie()
special_words = ["hello!", "world?", "test@domain.com", "user#123"]
for word in special_words:
    special_trie.insert(word)

print(f"Special words: {special_trie.get_all_words()}")
print(f"Search 'hello!': {special_trie.search('hello!')}")        # True
print(f"Prefix 'test@': {special_trie.starts_with('test@')}")     # True

# Unicode characters
unicode_trie = Trie()
unicode_words = ["café", "naïve", "résumé", "piñata", "αβγ"]
for word in unicode_words:
    unicode_trie.insert(word)

print(f"Unicode words: {unicode_trie.get_all_words()}")
print(f"Search 'café': {unicode_trie.search('café')}")           # True
print(f"Prefix 'rés': {unicode_trie.starts_with('rés')}")        # True

Large Data Handling

# Handling large datasets
import time

def benchmark_trie_operations():
    """Benchmark trie operations with large dataset."""
    trie = Trie()

    # Generate test data
    import string
    import random

    words = []
    for i in range(10000):
        length = random.randint(3, 15)
        word = ''.join(random.choices(string.ascii_lowercase, k=length))
        words.append(word)

    # Benchmark insertion
    start_time = time.time()
    for word in words:
        trie.insert(word)
    insert_time = time.time() - start_time

    print(f"Inserted {len(words)} words in {insert_time:.2f} seconds")
    print(f"Final trie size: {trie.size()}")

    # Benchmark search
    start_time = time.time()
    found_count = sum(1 for word in words[:1000] if trie.search(word))
    search_time = time.time() - start_time

    print(f"Searched 1000 words in {search_time:.4f} seconds")
    print(f"Found {found_count} words")

# Uncomment to run benchmark
# benchmark_trie_operations()

Practical Applications

Spell Checker Implementation

class SimpleSpellChecker:
    """A simple spell checker using trie."""

    def __init__(self):
        self.dictionary = Trie(case_sensitive=False)
        self._load_dictionary()

    def _load_dictionary(self):
        """Load common English words."""
        common_words = [
            "the", "be", "to", "of", "and", "a", "in", "that", "have",
            "i", "it", "for", "not", "on", "with", "he", "as", "you",
            "do", "at", "this", "but", "his", "by", "from", "they",
            "we", "say", "her", "she", "or", "an", "will", "my",
            "one", "all", "would", "there", "their", "what", "so",
            "up", "out", "if", "about", "who", "get", "which", "go",
            "me", "when", "make", "can", "like", "time", "no", "just",
            "him", "know", "take", "people", "into", "year", "your",
            "good", "some", "could", "them", "see", "other", "than",
            "then", "now", "look", "only", "come", "its", "over",
            "think", "also", "back", "after", "use", "two", "how",
            "our", "work", "first", "well", "way", "even", "new",
            "want", "because", "any", "these", "give", "day", "most", "us"
        ]

        for word in common_words:
            self.dictionary.insert(word)

    def is_spelled_correctly(self, word: str) -> bool:
        """Check if a word is spelled correctly."""
        return self.dictionary.search(word)

    def get_suggestions(self, word: str, max_suggestions: int = 5) -> List[str]:
        """Get spelling suggestions for a word."""
        if self.is_spelled_correctly(word):
            return [word]  # Word is correct

        # Try different prefix lengths
        suggestions = []
        for i in range(1, len(word) + 1):
            prefix = word[:i]
            prefix_suggestions = self.dictionary.autocomplete(prefix, max_suggestions)
            suggestions.extend(prefix_suggestions)
            if len(suggestions) >= max_suggestions:
                break

        # Remove duplicates and limit results
        return list(dict.fromkeys(suggestions))[:max_suggestions]

    def check_text(self, text: str) -> dict:
        """Check spelling of all words in text."""
        words = text.lower().split()
        results = {
            'correct': [],
            'incorrect': [],
            'suggestions': {}
        }

        for word in words:
            # Remove punctuation
            clean_word = ''.join(c for c in word if c.isalpha())
            if not clean_word:
                continue

            if self.is_spelled_correctly(clean_word):
                results['correct'].append(clean_word)
            else:
                results['incorrect'].append(clean_word)
                results['suggestions'][clean_word] = self.get_suggestions(clean_word)

        return results

# Usage example
spell_checker = SimpleSpellChecker()

# Test individual words
print(f"'hello' correct: {spell_checker.is_spelled_correctly('hello')}")    # True
print(f"'helo' correct: {spell_checker.is_spelled_correctly('helo')}")      # False

# Get suggestions
suggestions = spell_checker.get_suggestions('helo')
print(f"Suggestions for 'helo': {suggestions}")

# Check entire text
text = "The qick brown fox jumps ovr the lazy dog"
results = spell_checker.check_text(text)
print(f"Correct words: {results['correct']}")
print(f"Incorrect words: {results['incorrect']}")
for word, suggestions in results['suggestions'].items():
    print(f"  '{word}' -> {suggestions}")

Domain Name Router

class DomainRouter:
    """Route requests based on domain patterns using trie."""

    def __init__(self):
        self.routes = Trie(case_sensitive=False)
        self.handlers = {}

    def add_route(self, domain_pattern: str, handler: str):
        """Add a domain route."""
        # Reverse domain for prefix matching (com.example.api -> api.example.com)
        reversed_domain = '.'.join(reversed(domain_pattern.split('.')))
        self.routes.insert(reversed_domain)
        self.handlers[reversed_domain] = handler

    def route_request(self, domain: str) -> str:
        """Find handler for domain."""
        reversed_domain = '.'.join(reversed(domain.split('.')))

        # Try exact match first
        if self.routes.search(reversed_domain):
            return self.handlers[reversed_domain]

        # Try prefix matching
        for route in self.routes.get_all_words():
            if reversed_domain.startswith(route):
                return self.handlers[route]

        return "default_handler"

    def get_matching_patterns(self, domain: str) -> List[str]:
        """Get all patterns that could match the domain."""
        reversed_domain = '.'.join(reversed(domain.split('.')))
        matches = []

        for route in self.routes.get_all_words():
            if reversed_domain.startswith(route) or route.startswith(reversed_domain):
                # Convert back to normal domain format
                original_pattern = '.'.join(reversed(route.split('.')))
                matches.append(original_pattern)

        return matches

# Usage example
router = DomainRouter()

# Add routes
router.add_route("api.example.com", "api_handler")
router.add_route("admin.example.com", "admin_handler")
router.add_route("example.com", "main_handler")
router.add_route("subdomain.api.example.com", "subdomain_api_handler")

# Route requests
test_domains = [
    "api.example.com",
    "admin.example.com", 
    "www.example.com",
    "subdomain.api.example.com",
    "unknown.domain.com"
]

print("Domain routing results:")
for domain in test_domains:
    handler = router.route_request(domain)
    matches = router.get_matching_patterns(domain)
    print(f"  {domain} -> {handler} (patterns: {matches})")

IP Address Prefix Matching

class IPPrefixRouter:
    """Route IP addresses using longest prefix matching with trie."""

    def __init__(self):
        self.prefix_trie = Trie()
        self.routes = {}

    def _ip_to_binary(self, ip: str) -> str:
        """Convert IP address to binary string."""
        parts = ip.split('.')
        binary = ''
        for part in parts:
            binary += format(int(part), '08b')
        return binary

    def add_route(self, network: str, next_hop: str):
        """Add a network route (e.g., '192.168.1.0/24')."""
        ip, prefix_len = network.split('/')
        binary_ip = self._ip_to_binary(ip)
        prefix = binary_ip[:int(prefix_len)]

        self.prefix_trie.insert(prefix)
        self.routes[prefix] = {
            'network': network,
            'next_hop': next_hop,
            'prefix_length': int(prefix_len)
        }

    def route_ip(self, ip: str) -> dict:
        """Find best route for IP address (longest prefix match)."""
        binary_ip = self._ip_to_binary(ip)

        best_match = None
        longest_prefix = ""

        # Find longest matching prefix
        for route_prefix in self.prefix_trie.get_all_words():
            if binary_ip.startswith(route_prefix):
                if len(route_prefix) > len(longest_prefix):
                    longest_prefix = route_prefix
                    best_match = self.routes[route_prefix]

        return best_match or {'network': 'default', 'next_hop': 'default_gateway', 'prefix_length': 0}

    def get_routing_table(self) -> List[dict]:
        """Get all routes sorted by prefix length."""
        routes = list(self.routes.values())
        return sorted(routes, key=lambda x: x['prefix_length'], reverse=True)

# Usage example
ip_router = IPPrefixRouter()

# Add routes
ip_router.add_route("192.168.0.0/16", "gateway1")
ip_router.add_route("192.168.1.0/24", "gateway2")
ip_router.add_route("192.168.1.128/25", "gateway3")
ip_router.add_route("10.0.0.0/8", "gateway4")

# Test routing
test_ips = [
    "192.168.1.100",
    "192.168.1.200", 
    "192.168.2.100",
    "10.0.1.1",
    "8.8.8.8"
]

print("IP routing results:")
for ip in test_ips:
    route = ip_router.route_ip(ip)
    print(f"  {ip} -> {route['next_hop']} (network: {route['network']})")

print(f"\nRouting table:")
for route in ip_router.get_routing_table():
    print(f"  {route['network']} -> {route['next_hop']}")

Performance Considerations

Memory Usage

def analyze_trie_memory():
    """Analyze memory usage patterns of trie."""
    import sys

    # Create tries with different characteristics
    sparse_trie = Trie()  # Few words, little sharing
    dense_trie = Trie()   # Many words, lots of sharing

    # Sparse trie - completely different words
    sparse_words = ["apple", "zebra", "moon", "fire", "water"]
    for word in sparse_words:
        sparse_trie.insert(word)

    # Dense trie - many shared prefixes
    dense_words = []
    prefixes = ["pro", "pre", "sub", "super", "anti"]
    suffixes = ["gram", "fix", "marine", "sonic", "body"]
    for prefix in prefixes:
        for suffix in suffixes:
            dense_words.append(prefix + suffix)

    for word in dense_words:
        dense_trie.insert(word)

    print(f"Sparse trie: {len(sparse_words)} words")
    print(f"Dense trie: {len(dense_words)} words")
    print(f"Memory efficiency: Dense trie has {len(dense_words)/len(sparse_words):.1f}x more words")

    # Show prefix sharing benefits
    print(f"\nPrefix sharing in dense trie:")
    for prefix in ["pro", "pre", "sub"]:
        count = dense_trie.count_words_with_prefix(prefix)
        print(f"  '{prefix}' prefix: {count} words")

# analyze_trie_memory()

Best Practices

def trie_best_practices():
    """Demonstrate best practices for trie usage."""

    # 1. Choose appropriate case sensitivity
    # For user input/search: case-insensitive
    search_trie = Trie(case_sensitive=False)

    # For exact string matching: case-sensitive
    code_trie = Trie(case_sensitive=True)

    # 2. Batch operations for better performance
    words_to_insert = ["word1", "word2", "word3", "word4"]

    # Good: batch insert
    for word in words_to_insert:
        search_trie.insert(word)

    # 3. Use specific methods for specific needs
    # For existence check: use search()
    exists = search_trie.search("word1")

    # For prefix check: use starts_with()
    has_prefix = search_trie.starts_with("wor")

    # For counting: use count_words_with_prefix()
    count = search_trie.count_words_with_prefix("wor")

    # For limited results: use autocomplete()
    suggestions = search_trie.autocomplete("wor", max_suggestions=5)

    # 4. Consider memory vs. functionality trade-offs
    print("Best practices applied!")

    return {
        'search_trie_size': search_trie.size(),
        'code_trie_size': code_trie.size(),
        'example_exists': exists,
        'example_prefix': has_prefix,
        'example_count': count,
        'example_suggestions': suggestions
    }

# Example usage
results = trie_best_practices()
print("Results:", results)

API Reference

Trie (Prefix Tree) Implementation

A trie is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It's particularly efficient for operations involving prefixes, such as autocomplete functionality.

Key Features:

Word insertion, search, and deletion
Prefix-based operations (starts_with, get_words_with_prefix)
Autocomplete functionality
Memory-efficient storage of strings with common prefixes
Case-sensitive and case-insensitive modes

Time Complexities:

Insert: O(m) where m is the length of the word
Search: O(m) where m is the length of the word
Delete: O(m) where m is the length of the word
Prefix operations: O(p + n) where p is prefix length and n is number of results

Space Complexity: O(ALPHABET_SIZE * N * M) where N is number of words and M is average length

`Trie(case_sensitive=True)`

Bases: TrieInterface

A trie (prefix tree) implementation for efficient string storage and retrieval.

This implementation supports case-sensitive and case-insensitive modes, and provides comprehensive prefix-based operations.

Initialize a trie.

Parameters:

Name	Type	Description	Default
`case_sensitive`	`bool`	Whether the trie should be case-sensitive	`True`

`contains(word)`

Check if a word is in the trie using 'in' operator.

`iter()`

Iterate over all words in the trie.

`len()`

Return the number of words in the trie.

`repr()`

Return detailed representation for debugging.

`str()`

Return string representation of the trie.

`autocomplete(prefix, max_suggestions=10)`

Get autocomplete suggestions for a given prefix.

Parameters:

Name	Type	Description	Default
`prefix`	`str`	Prefix to get suggestions for	required
`max_suggestions`	`int`	Maximum number of suggestions to return	`10`

Returns:

Type	Description
`List[str]`	List of suggested words (up to max_suggestions)

`contains_prefix(word)`

Check if the trie contains any prefix of the given word.

Parameters:

Name	Type	Description	Default
`word`	`str`	Word to check prefixes for	required

Returns:

Type	Description
`bool`	True if any prefix is found, False otherwise

`count_words_with_prefix(prefix)`

Count the number of words that start with the given prefix.

Parameters:

Name	Type	Description	Default
`prefix`	`str`	Prefix to count words for	required

Returns:

Type	Description
`int`	Number of words with the prefix

`delete(word)`

Delete a word from the trie.

Parameters:

Name	Type	Description	Default
`word`	`str`	Word to delete	required

Returns:

Type	Description
`bool`	True if word was deleted, False if not found

`get_all_words()`

Get all words stored in the trie.

Returns:

Type	Description
`List[str]`	List of all words in the trie

`get_longest_common_prefix()`

Get the longest common prefix of all words in the trie.

Returns:

Type	Description
`str`	Longest common prefix string

`get_shortest_unique_prefix(word)`

Get the shortest unique prefix for a word.

Parameters:

Name	Type	Description	Default
`word`	`str`	Word to find unique prefix for	required

Returns:

Type	Description
`Optional[str]`	Shortest unique prefix, or None if word not in trie

`get_words_with_prefix(prefix)`

Get all words that start with the given prefix.

Parameters:

Name	Type	Description	Default
`prefix`	`str`	Prefix to search for	required

Returns:

Type	Description
`List[str]`	List of words starting with the prefix

`insert(word)`

Insert a word into the trie.

Parameters:

Name	Type	Description	Default
`word`	`str`	Word to insert	required

`is_empty()`

Check if the trie is empty.

Returns:

Type	Description
`bool`	True if trie is empty, False otherwise

`search(word)`

Search for a word in the trie.

Parameters:

Name	Type	Description	Default
`word`	`str`	Word to search for	required

Returns:

Type	Description
`bool`	True if word exists, False otherwise

`size()`

Get the number of words in the trie.

Returns:

Type	Description
`int`	Number of words stored

`starts_with(prefix)`

Check if any word in the trie starts with the given prefix.

Parameters:

Name	Type	Description	Default
`prefix`	`str`	Prefix to check	required

Returns:

Type	Description
`bool`	True if any word starts with prefix, False otherwise

`TrieNode(char=None, is_end=False)`

Bases: TrieNodeInterface

A node in the trie structure.

Each node represents a character and maintains references to child nodes and a flag indicating if it marks the end of a word.

Initialize a trie node.

Parameters:

Name	Type	Description	Default
`char`	`Optional[str]`	The character this node represents (None for root)	`None`
`is_end`	`bool`	Whether this node marks the end of a word	`False`

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the node.

`add_child(char)`

Add a child node for the given character.

Parameters:

Name	Type	Description	Default
`char`	`str`	Character for the new child node	required

Returns:

Type	Description
`TrieNode`	The child node (new or existing)

`get_child(char)`

Get the child node for the given character.

Parameters:

Name	Type	Description	Default
`char`	`str`	Character to look for	required

Returns:

Type	Description
`Optional[TrieNode]`	Child node if exists, None otherwise

`get_children_chars()`

Get list of characters for all child nodes.

Returns:

Type	Description
`List[str]`	List of characters that have child nodes

`has_child(char)`

Check if a child exists for the given character.

Parameters:

Name	Type	Description	Default
`char`	`str`	Character to check	required

Returns:

Type	Description
`bool`	True if child exists, False otherwise

`has_children()`

Check if this node has any children.

Returns:

Type	Description
`bool`	True if node has children, False otherwise

`remove_child(char)`

Remove the child node for the given character.

Parameters:

Name	Type	Description	Default
`char`	`str`	Character of child to remove	required

Returns:

Type	Description
`bool`	True if child was removed, False if not found

Trie (Prefix Tree)

Features

Time Complexities

Basic Usage

Creating and Initializing

Creating Nodes

Basic Word Operations

Word Insertion

Single Word Insertion

Multiple Word Insertion

Handling Duplicates

Prefix Relationships

Case Sensitivity

Case-Sensitive Mode (Default)

Case-Insensitive Mode

Handling Empty Strings

Prefix Operations

Checking Prefixes

Getting Words with Prefix

Counting Words with Prefix

Getting All Words

Autocomplete Functionality

Basic Autocomplete

Limited Autocomplete

Real-world Autocomplete Example

Word Deletion

Basic Deletion

Deleting Prefix Words

Deleting Non-existent Words

Deleting Last Word

Advanced Operations

Longest Common Prefix

Shortest Unique Prefix

Contains Prefix Check

Iteration and Traversal

Iterating Over Words

Using Built-in Functions

String Representation and Debugging

String Representations

Node Representations

Error Handling and Edge Cases

Empty Trie Operations

Special Characters and Unicode

Large Data Handling

Practical Applications

Spell Checker Implementation

Domain Name Router

IP Address Prefix Matching

Performance Considerations

Memory Usage

Best Practices

API Reference

Trie(case_sensitive=True)

__contains__(word)

__iter__()

__len__()

__repr__()

__str__()

autocomplete(prefix, max_suggestions=10)

contains_prefix(word)

count_words_with_prefix(prefix)

delete(word)

get_all_words()

get_longest_common_prefix()

get_shortest_unique_prefix(word)

get_words_with_prefix(prefix)

insert(word)

is_empty()

search(word)

size()

starts_with(prefix)

TrieNode(char=None, is_end=False)

__repr__()

__str__()

add_child(char)

get_child(char)

get_children_chars()

has_child(char)

has_children()

remove_child(char)

`Trie(case_sensitive=True)`

`contains(word)`

`iter()`

`len()`

`repr()`

`str()`

`autocomplete(prefix, max_suggestions=10)`

`contains_prefix(word)`

`count_words_with_prefix(prefix)`

`delete(word)`

`get_all_words()`

`get_longest_common_prefix()`

`get_shortest_unique_prefix(word)`

`get_words_with_prefix(prefix)`

`insert(word)`

`is_empty()`

`search(word)`

`size()`

`starts_with(prefix)`

`TrieNode(char=None, is_end=False)`

`repr()`

`str()`

`add_child(char)`

`get_child(char)`

`get_children_chars()`

`has_child(char)`

`has_children()`

`remove_child(char)`