LeetCode 208 – Implement Trie (Prefix Tree)

Implement Trie is a build-the-data-structure question, and the structure is simple enough that the interview is really about two things: whether you can explain why a trie beats a hash set for prefix queries, and whether you remember the one field that separates a word from a prefix.

The problem

Implement a trie supporting:

• insert(word)
• search(word) — is this exact word in the trie?
• startsWith(prefix) — is any inserted word prefixed by this?

insert("apple")
search("apple")     -> true
search("app")       -> false     inserted as a PREFIX, not as a word
startsWith("app")   -> true
insert("app")
search("app")       -> true      now it is a word too

Those two search("app") calls returning different answers is the whole design constraint, and it is what the isWord flag exists for.

Why not a hash set

A HashSet<String> answers insert and search in O(L), better constant factor and less code. It cannot answer startsWith without scanning every stored word.

The trie's structure is the prefix relation: every path from the root spells a prefix, so "does any word start with this?" becomes "does this path exist?" — O(L), independent of how many words are stored. That is the trade, and stating it is the answer to "why this and not a set".

insert "app", "apple", "apply"

root -a- -p- -p*- -l- -e*
                    \
                     -y*        * = isWord

one shared path for the common prefix; three words, five nodes past the root

The node, and the flag

Each node holds children and a boolean. The boolean is the only thing distinguishing a node that ends a word from one that is merely passed through — the node for "app" exists either way, and without the flag search and startsWith would be the same method.

Java

class Trie {
    private static class Node {
        // 26 slots: the problem guarantees lowercase English letters only.
        Node[] children = new Node[26];
        boolean isWord;                  // the ONLY thing separating a word from a prefix
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;

        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Node();
            node = node.children[i];
        }

        node.isWord = true;
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isWord;   // must be a WORD, not just a path
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;          // the path existing is enough
    }

    /** The node reached by following the string, or null if the path breaks. */
    private Node walk(String text) {
        Node node = root;

        for (char c : text.toCharArray()) {
            node = node.children[c - 'a'];
            if (node == null) return null;
        }

        return node;
    }
}

search and startsWith differ by exactly one clause, which is the design made visible. Factoring the shared descent into walk is worth doing for that reason as much as for the duplication.

A fixed Node[26] is faster than a HashMap and assumes lowercase ASCII — state that assumption. For a large alphabet, or a sparse trie where most nodes have one child, a map uses far less memory, and that trade is a common follow-up.

Python

class Trie:
    def __init__(self):
        self.children: dict[str, "Trie"] = {}
        self.is_word = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            node = node.children.setdefault(c, Trie())
            # setdefault creates the child only if it is missing
        node.is_word = True

    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

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

Using the Trie class as its own node type removes a class and makes the recursive structure obvious — a trie is a node whose children are tries. setdefault(c, Trie()) is the create-if-absent idiom, though note it constructs the Trie() argument even when the key exists; a defaultdict or an explicit check avoids that allocation if it matters.

A dict rather than a fixed array means the alphabet assumption disappears — this trie stores any characters at all.

Complexity

L is the length of the word, and — this is the point — none of the operations depend on how many words are stored. A trie with a million words answers startsWith in the same time as one with ten.

The space is the honest weakness. With a 26-slot array per node, a trie of one long word allocates 26 pointers per character. Sharing prefixes is what pays for it, so a trie is a good structure for dense dictionaries and a poor one for a handful of unrelated strings.

The follow-ups

delete(word) is the one that exposes whether the structure is understood. Clear isWord, then remove nodes on the way back up — but only while they have no children and are not themselves words. Deleting "app" from a trie also containing "apple" must remove nothing.

Add and Search Word (211) allows . as a wildcard, which turns search into a DFS branching over all children at each dot. Word Search II (212) walks a grid against a trie, which is the classic use — one traversal tests thousands of words at once, and that is impossible with a set.

Storing a value per word turns this into a prefix-queried map, which is what autocomplete and IP routing tables actually use.

What the interviewer is checking

• The isWord flag, and that search("app") is false before it is inserted.
• That you can say why a hash set cannot do startsWith.
• That search and startsWith share a descent and differ by one clause.
• The alphabet assumption, stated rather than assumed.
• The empty string, and inserting the same word twice.
• That operations are independent of the number of stored words.
• The space cost, and when a trie is the wrong choice.