Trie

A trie (prefix tree) stores strings character-by-character. Each path from root to a marked node spells one stored word. Tries excel at prefix queries, autocomplete, and shared-prefix compression.

When to use a trie

Scenario	Why trie
Prefix search (“all keys starting with pre”)	Natural O(L) walk
Autocomplete / dictionary	Branch per character
Word search on grid	Trie + backtracking
XOR maximum of binary strings	Bitwise trie variant
Spell checker / IP routing (conceptually)	Longest prefix match

Prefer dict / set when you only need exact word lookup, not prefix structure.

Complexity

Let L = word length, N = number of words stored, A = alphabet size (26 for lowercase letters).

Operation	Time	Space
Insert word	O(L)	O(L) new nodes worst case
Exact search	O(L)	O(1) extra
Prefix search (startsWith)	O(L)	O(1) extra
Delete word	O(L)	O(1) extra
Store N words total	—	O(total characters) ≤ O(N · L)

Compared to hash table: trie uses more space for sparse prefixes but wins on prefix and lexicographic ordering operations.

Structure

Each node holds:

• children — map char → child node
• is_end_of_word — whether a word ends here

Implementation

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_end_of_word = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def delete(self, word: str) -> None:
        def _delete(node: TrieNode, index: int) -> bool:
            if index == len(word):
                if not node.is_end_of_word:
                    return False
                node.is_end_of_word = False
                return len(node.children) == 0
            char = word[index]
            if char not in node.children:
                return False
            should_prune = _delete(node.children[char], index + 1)
            if should_prune:
                del node.children[char]
                return len(node.children) == 0 and not node.is_end_of_word
            return False

        _delete(self.root, 0)

    def words_with_prefix(self, prefix: str) -> list[str]:
        node = self._find_node(prefix)
        if node is None:
            return []
        results: list[str] = []

        def dfs(n: TrieNode, path: str) -> None:
            if n.is_end_of_word:
                results.append(path)
            for ch, child in n.children.items():
                dfs(child, path + ch)

        dfs(node, prefix)
        return results

Insert/search/prefix: O(L) time, O(1) auxiliary space per call.
Delete: O(L) time; may prune unused nodes.

Array vs map children

Child storage	Pros	Cons
dict[str, TrieNode]	Sparse alphabet, flexible	Pointer overhead
Fixed array size 26	Fast index ord(c) - ord('a')	Wastes space if sparse

Use dict in Python interviews unless problem fixes alphabet to lowercase a–z.

Trie vs hash set

	Trie	set of strings
Exact lookup	O(L)	O(L) hash
Prefix queries	O(L)	O(N) scan all strings
Space	Shared prefixes	Each string stored fully
Lexicographic iterate	DFS order	Sort required

Common patterns

1. Store reversed words — palindrome pairing problems.
2. Bit trie — each node has 0 and 1 child; used for maximum XOR subarray.
3. Trie + DFS on grid — prune when prefix not in trie.

Related pages

• Hashing — exact string lookup alternative
• Tree — general hierarchical structure
• Graph — grid word search as graph DFS