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?

To make this concrete, imagine you are building an autocomplete system. You insert words like "apple", "app", and "apricot". If a user types "app", startsWith("app") should return true because there are words starting with that prefix, and search("app") should also return true because we explicitly inserted "app". However, search("ap") would return false because we never inserted "ap" as a standalone word, even though startsWith("ap") is true. We can assume all inputs consist entirely of lowercase English letters a-z, and words can be up to 2000 characters long.

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.

Think of a trie like a massive physical file cabinet system. The first cabinet is labeled with the first letter of the word, the drawer inside is labeled with the second letter, and a folder inside is labeled with the third letter. If you want to find "cat", you go to the C cabinet, pull the A drawer, and grab the T folder. If you want "car", you use the exact same C cabinet and A drawer, but look for the R folder instead. The prefix "ca" is shared, saving space and time.

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.

Trace

Let's trace insert("cat") and then search("ca").

1. insert("cat")
   • Start at root.
   • c: not in children. Add it. Move to c node.
   • a: not in children. Add it. Move to a node.
   • t: not in children. Add it. Move to t node.
   • End of word: set t_node.is_word = True.
2. search("ca")
   • Call _walk("ca").
   • c is in root's children, move to c node.
   • a is in c's children, move to a node.
   • Loop ends. Return a node.
   • In search, node is not None, but node.is_word is False. Return False.

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.

Let's break this down:

• Time Complexity: To insert or search for a word, we step through each of its characters exactly once. For a word of length L, we perform L steps. At each step, we look up a character in a hash map (or index into a 26-slot array), which takes constant O(1) time. Thus, the total time is L \times O(1) = O(L).
• Space Complexity: Every character in the worst case (e.g., if no words share any prefixes, like "cat" and "dog") requires a new node. If we insert N words of average length L, we could create up to N \times L nodes. Therefore, space complexity is bounded by O(\text{total characters inserted}). In practice, because prefixes are shared, the actual memory footprint is significantly smaller.

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.