Trie (Prefix Tree)

Concept

A trie is a tree where each edge is a character. Words sharing a prefix share the same path, so searching a prefix of length L takes O(L) regardless of how many words exist.

Each node holds a map of children and an end-of-word flag. Insert walks/creates nodes; search walks and checks the flag; startsWith just walks.

Binary (XOR) tries store numbers bit by bit from the highest bit — used to find the maximum XOR of two numbers in O(n · 32).

Complexity

Code (Python)

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

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

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

    def search(self, word):
        node = self._walk(word)
        return bool(node and node.end)

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Remember

• Prefix queries over many words → trie.
• Combine trie + DFS for Word Search II.
• Bitwise trie solves max-XOR problems.