Trie Implementation and Operations
Hardinsert, search, startsWith
Problem
Implement a trie (prefix tree) supporting insert(word), search(word), and startsWith(prefix).
A tree of letters: follow one letter per level to store and look up words fast.
The idea
A trie stores words as paths of characters, so words sharing a prefix share the nodes for that prefix. Insert walks the path creating missing nodes, search walks it and checks the end-of-word flag, and startsWith walks it and simply checks the path exists — the flag is the only difference between the last two.
The trick
- Every operation is O(length of the word), independent of how many words are stored.
- search and startsWith are the same walk; only the final check differs.
- The end-of-word flag is what stops 'app' matching when only 'apple' was inserted.
Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.
Descend one node per letter.
1insert(word) {2 let node = this.root;3 for (const ch of word) {4 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5 node = node.children.get(ch);6 }7 node.isEnd = true;8}Input
- nodes
- 5, 4 edges
Memory
- matched
- —
Output
- created
- —
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- insert 'apple'; search 'apple'
- Output:
- true
Example 2
- Input:
- search 'app'
- Output:
- false
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.