Trees

Trie

TimeO(m) SpaceO(n * m)

Think of autocomplete on your phone. As you type “h-e-l,” the system instantly narrows to words starting with “hel” — hello, help, helmet. A trie stores words letter by letter along branching paths, so shared prefixes share nodes. Typing each letter just follows one edge.

When to use it: Prefix matching, autocomplete, spell checking, word search in a grid, or any problem that asks “does any word start with this prefix?”

Key insight: Each node represents a character, and the path from root to a node spells out a prefix. Lookup time depends only on the length of the query string, not the number of stored words.

Common trap: Excessive memory usage. Each node may have up to 26 children (for lowercase English). For sparse tries, use a hash map instead of an array at each node.

class TrieNode:
    children = {}                   # char -> TrieNode
    isEndOfWord = false

class Trie:
    root = new TrieNode()

function insert(word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = new TrieNode()
        node = node.children[char]
    node.isEndOfWord = true         # mark end of complete word

function search(word):
    node = root
    for char in word:
        if char not in node.children:
            return false
        node = node.children[char]
    return node.isEndOfWord         # must be a complete word, not just prefix

function startsWith(prefix):
    node = root
    for char in prefix:
        if char not in node.children:
            return false
        node = node.children[char]
    return true                     # prefix exists

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = 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 = True

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

    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 words_with_prefix(self, prefix: str) -> list[str]:
        """Return all words that start with the given prefix."""
        node = self._find_node(prefix)
        if not node:
            return []

        results = []
        self._collect(node, list(prefix), results)
        return results

    def _collect(self, node: TrieNode, path: list[str], results: list[str]) -> None:
        if node.is_end:
            results.append("".join(path))
        for char, child in node.children.items():
            path.append(char)
            self._collect(child, path, results)
            path.pop()

Problem: Design a data structure that supports adding words and searching for words, where searches can contain the wildcard character '.' that matches any single letter.

How would you approach this?

Answer: This is a trie problem. Insert words normally. For search, when encountering '.', recursively try all children at that node. The trie structure makes this efficient because you only branch at wildcard positions.

Problem: Given a 2D board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (up/down/left/right).

How would you approach this?

Answer: This is trie + DFS backtracking. Build a trie from the word list, then DFS from each cell. The trie lets you prune paths early — if no word in the list starts with the current prefix, stop exploring that direction.

Time: O(m) per operation (insert, search, startsWith) where m is the length of the word or prefix. Each character requires one hash map lookup and one step down the tree.

Space: O(n * m) in the worst case, where n is the number of words and m is the average word length. Each character in each word may create a new node. In practice, shared prefixes reduce this significantly.