Trie

A Trie (Prefix Tree) is an ordered tree data structure used to store strings. Each node represents a single character, and shared prefixes share the same node paths. This allows constant time retrieval proportional to key length, regardless of dictionary size.

Complexity Profile

Case	Complexity
Best Case	O(L) - Key Length
Average Case	O(L)
Worst Case	O(L)
Space Complexity	O(ALPHABET_SIZE * N * L)

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end_of_word = True
        
    def search(self, word):
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end_of_word

Real-World Applications

• Autocomplete widgets on search bars.
• IP routing lookup tables.
• Spell checkers and dictionary validation tools.