4.15.1 — Implement Trie (Prefix Tree)

LeetCode 208 · Medium · ★ Blind 75

The problem

Build a data structure with three operations:

• insert(word)
• search(word) — is this exact word stored?
• startsWith(prefix) — is any stored word starting with this prefix?

The pattern

A hash set answers search in O(1), but it cannot answer startsWith at all without checking every stored word. Prefix questions need a structure organised by prefix, and that is a trie.

A trie is a tree where each edge is a character and each path from the root spells a prefix. Words sharing a prefix share the nodes for it.

inserting "cat", "car", "dog":

        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t   r    g
    ●   ●    ●        ● marks the end of a word

"ca" is a real path but has no ●, so it is a prefix and not a stored word. That distinction is why the flag exists.

The flag that makes it work

Without a marker, search("ca") and startsWith("ca") would give the same answer, and the structure could not tell a stored word from an intermediate step.

So each node carries is_word. Then:

• search — walk the characters, then check the flag.
• startsWith — walk the characters, and stop. The flag is irrelevant.

Those two methods differ by exactly one line, which is the cleanest way to see what the flag is for.

The solution

Python

class TrieNode:
    def __init__(self):
        self.children = {}          # character → TrieNode
        self.is_word = False


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

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

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

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

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

TypeScript

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isWord = true;
  }

  private walk(prefix: string): TrieNode | null {
    let node = this.root;
    for (const c of prefix) {
      const next = node.children.get(c);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isWord;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}

Pulling the shared walk into a helper is not just tidiness — it makes the one-line difference between search and startsWith visible, which is exactly what an interviewer wants to see you understand.

Map or array for the children?

Both are used, and the choice is a real trade.

A 26-slot array is faster — indexing beats hashing — and it makes the code slightly shorter. But every node allocates 26 slots whether it uses them or not, which wastes memory on sparse tries, and it only works for a known small alphabet.

A hash map allocates only what is used and handles any alphabet, including Unicode.

For lowercase English with dense data, the array wins. For anything else, the map. Say which you chose and why — this is the design decision the problem is really testing.

Complexity

For a word of length L:

• insert, search, startsWith — all O(L).

Note what is not in that bound: the number of stored words. A trie's lookup cost depends only on the length of the key, not on how many keys exist. That is the property that makes it useful.

Space is O(\text{total characters}) in the worst case, and much less in practice because shared prefixes are stored once.

Trie or hash set?

	trie	hash set
exact lookup	O(L)	O(L) to hash, then O(1)
prefix queries	O(L)	impossible without a full scan
sorted iteration	free, in order	needs a separate sort
memory	shares prefixes	stores every key whole

Use a trie when prefixes matter. For exact membership alone, a hash set is simpler and usually faster.

Where this appears

• Autocomplete — walk to the prefix node, then collect the words below it. Chapter 11.11 builds this as a system.
• IP routing — a router matches the longest prefix of a destination address, using a trie over bits rather than characters. Chapter 5.3.2.
• Spell checkers and word games — 4.15.3 Word Search II is the clearest example.
• Compressed tries (radix trees) — merge chains of single-child nodes into one edge holding a whole string. Far less memory, and it is what real routing tables use. 4.13.4 covers it.

What the interviewer will push on

"Why not a hash set?" It cannot answer prefix queries.

"Why does each node need a flag?" To tell a stored word from an intermediate prefix. Give "ca" versus "cat".

"Array or map for the children?" State the memory-versus-speed trade and the alphabet assumption.

"How would you implement delete?" Walk down, clear the flag, then unlink nodes on the way back up only while they have no children and are not word endings. That reverse pass is the interesting part.

"How would you return all words with a prefix?" Walk to the prefix node, then DFS below it collecting every node with the flag set.

One thing to volunteer: point out that the cost depends on key length only, not on how many words are stored. That is the property that justifies the structure.

Next: 4.15.2 Design Add and Search Words — the same trie, with a wildcard that forces the search to branch.