Implement Trie (Prefix Tree)
Implement Trie (Prefix Tree)
Implement a Trie (prefix tree) data structure with the following operations: - INSERT word: insert the word into the trie - SEARCH word: return YES if the exact word exists, NO otherwise - STARTSWITH prefix: return YES if any inserted word starts with prefix, NO otherwise
Input format — only if your code reads from stdin
Input format: - First line: integer q (number of operations) - Next q lines: each line is "INSERT word", "SEARCH word", or "STARTSWITH prefix" Output: for each SEARCH or STARTSWITH operation, print YES or NO on its own line.
Approach
A Trie node has 26 children (one per letter) and an isEnd flag. INSERT: for each character create node if absent, then mark last node as end. SEARCH: traverse characters, return false if any node missing, return isEnd of last node. STARTSWITH: same as SEARCH but return true as long as all characters exist.
Input
Output
- •
1 ≤ q ≤ 3×10^4, all words/prefixes consist of lowercase English letters
More Trees problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards