Implement Trie
Mediuminsert · search · startsWith
Store each word as a path of letters; to look one up, just walk the path.
The idea
Insert walks/creates a path of nodes and flags the last as a word end. search does the same walk and checks the flag; startsWith just checks the path exists.
Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.
1/5
Optimal
timeO(L)spaceO(L)
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("app")
- Output:
- false
- Explanation:
- The walk reaches a real node, but that node's isEnd flag is false — "app" is a prefix here, not a stored word.
Example 2
- Input:
- insert("app") then search("app")
- Output:
- true
- Explanation:
- No new nodes are created; the existing node's isEnd is simply set. That flag is the whole difference between the two operations.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.