Implement Trie (Prefix Tree)
Implement a Trie (Prefix Tree) data structure that supports the following operations:
- insert(word) — Inserts a word into the Trie.
- search(word) — Returns true if the word exists in the Trie.
- startsWith(prefix) — Returns true if any previously inserted word starts with the given prefix.
All words consist of lowercase English letters.
Example 1
Input
n = 5 insert apple search apple search app startsWith app startsWith bat
Output
true false true false
Explanation
After inserting apple:
- search("apple") → true
- search("app") → false because app itself was not inserted.
- startsWith("app") → true because apple starts with app.
- startsWith("bat") → false.
Example 2
Input
n = 6 insert hello insert help search hello search hell startsWith hel startsWith wor
Output
true false true false
Explanation
Both hello and help are stored.
Therefore, hel is a valid prefix, but hell is not a complete inserted word.
Constraints
Hints:
Hint 1
Each Trie node represents one character of a word.
Hint 2
For every character, move to the corresponding child node. Mark the final node with isEnd = true when inserting a complete word.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 20, 2026
Last updated
Aug 20, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output