Trie (Prefix Tree)

A Trie is a tree where each path from root to node represents a prefix. It's the data structure behind autocomplete, spell checkers, and IP routing tables. If you're doing anything with prefixes, think Trie.

The Core Idea

Each node represents a character. A path from root spells out a string. Mark certain nodes as "end of word" to indicate complete words. Shared prefixes share paths - that's the magic.

Trie Implementation

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._find(prefix) is not None

    def _find(self, s):
        node = self.root
        for char in s:
            if char not in node.children:
                return None
            node = node.children[char]
        return node