208. Implement Trie

208

MediumTrie and Advanced String SearchTrie (character-indexed tree)Prefix tree construction and traversal

Implement Trie

Design a Trie (prefix tree) supporting three operations: insert(word) adds a word; search(word) returns true only if the exact word was inserted; startsWith(prefix) returns true if any inserted word begins with the given prefix.

Open official problem prompt ↗

In plain English

Build a dictionary structure that answers both exact-word and prefix-existence queries in time proportional to the query length, independent of how many words are stored.

Picture it like this

Like a physical library index where each drawer is a letter: to file or find a word you follow drawer 'a', then 'p', then 'p'... and a small flag on a drawer means 'a complete word ends here', not just 'more words continue past here'.

Example

Input: insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output: [null, true, false, true, null, true]
Why: 'apple' is present so search('apple') is true; 'app' was not inserted yet so search('app') is false but startsWith('app') is true; after inserting 'app', search('app') becomes true.

Constraints

1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English lettersAt most 3 * 10^4 calls in total to insert, search, and startsWith

Pattern lesson

See the pattern, then code

Prefix tree construction and traversal

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Store words letter by letter down a tree where each edge is a character; a boolean end-of-word flag distinguishes a full word from a mere prefix path.

New words, made simpleKnow these before the algorithm

Trie / prefix tree: A tree where each root-to-node path spells a prefix and edges are labeled by characters.
End-of-word flag: A boolean marking that the path to this node forms a complete inserted word.
Prefix sharing: Words with common leading characters share the same upper nodes, saving space.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash set of words

Prefix queries become linear in the dictionary size, which the trie avoids.

Store words in a set; search is O(L) but startsWith requires scanning every stored word.

Time search O(L), startsWith O(N*L)Space O(total chars)

Best choiceCharacter-indexed trie

Every operation is bounded by the query length and prefixes are shared.

One node per distinct prefix, each with a children map and an end flag.

Time O(L) per operationSpace O(total chars)

The rule we keep true

Invariant

For any inserted word, there is exactly one root-to-node path spelling it whose final node has is_end == True; every node reachable from the root corresponds to a prefix of at least one inserted word.

Why this is correct

Reasoning

insert guarantees the path and end flag exist; search re-walks that same deterministic path and additionally checks is_end so prefixes are not mistaken for words; startsWith omits the flag check because a mere existing path proves some word shares that prefix.

The algorithm in three movesSay these aloud before coding

1Represent each node as a map from character to child node plus an is_end flag

root -> a -> p -> p -> l -> e

2insert: walk or create nodes for each character, then mark the last node is_end

node 'e' has is_end = True

3search: walk the characters; succeed only if the path exists and the final node has is_end set

search('app'): path exists but is_end False -> False before insert('app')

4startsWith: walk the characters; succeed if the whole path merely exists

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'apple'

2 · AskWhich nodes exist?

3 · Update statechain a-p-p-l-e, is_end at e

4 · ResultWord stored

Key takeaway

Inserting 'apple' creates a single chain of five character nodes ending with is_end at 'e'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-4Node shape
Each Trie object is a node with a children map and an end flag; the object itself is the root.
2
Lines 6-12insert
Create missing child nodes along the path, then flag the final node.
3
Lines 14-16search
Reuse _find and require the terminal node's is_end to be true.
4
Lines 18-19startsWith
Only the existence of the path matters, so no end-flag check.
5
Lines 21-27_find helper
Walks the characters, returning the final node or None if the path breaks.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Searching a word never inserted returns false even if it is a prefix of a stored word
A word that is a prefix of another (e.g. 'app' under 'apple') needs its own is_end
Inserting the same word twice is harmless
Empty-string handling is not required given the length constraints

Common beginner mistakes

Returning true from search for a prefix that was never inserted as a whole word (forgetting the is_end check)
Sharing a single mutable default children dict across nodes
Confusing search (needs is_end) with startsWith (does not)
Not creating intermediate nodes during insert

Check your understanding

Two words 'app' and 'apple' are both inserted; how does the trie distinguish search('app') = true from a case where only 'apple' was inserted?

PyPython 3 · solution.py

Optimal

1class Trie:2    def __init__(self):3        self.children = {}4        self.is_end = False56    def insert(self, word: str) -> None:7        node = self8        for ch in word:9            if ch not in node.children:10                node.children[ch] = Trie()11            node = node.children[ch]12        node.is_end = True1314    def search(self, word: str) -> bool:15        node = self._find(word)16        return node is not None and node.is_end1718    def startsWith(self, prefix: str) -> bool:19        return self._find(prefix) is not None2021    def _find(self, word: str):22        node = self23        for ch in word:24            if ch not in node.children:25                return None26            node = node.children[ch]27        return node

Time complexityO(L) per operation, where L is the word/prefix lengthOptimized

Space complexityO(total characters inserted)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoftBloomberg

Implement Trie

Implement Trie

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search