Implement Trie (Prefix Tree)
The problem
Implement insert(word), search(word), and startsWith(prefix) for lowercase words. Search requires a whole stored word; startsWith only requires a matching prefix.
Example
After inserting "planet": search("plan") → false; startsWith("plan") → true
Need a hint?
A path and a complete word are different states.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Store child edges by character and an end-of-word flag at each node. Insert creates missing nodes then marks the endpoint. Both lookups walk the requested path; search additionally checks the flag. Prefix lookup succeeds when its path exists.
Complexity
O(L) time per operation for length L; O(total inserted characters) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.