Trie (Prefix Tree) Implementation / Usage

Trie (Prefix Tree) Implement a Trie that supports the following operations: insert(word): insert a lowercase word (a-z) search(word): return whether the exact word exists in the trie startsWith(prefix): return whether any inserted word starts with prefix Input (stdin) The first line contains an integer q, the number of operations. The next q lines each contain one operation: insert <word> search <word> startsWith <prefix> Output (stdout) For each search or startsWith operation, print true or false on its own line. Constraints 1 <= q <= 2 * 10^5 1 <= word.length <= 50 Total characters across all operations <= 2 * 10^6 Examples Example Input 8 insert apple search apple search app startsWith app insert app search app startsWith appl startsWith banana Output true false true true true false