A trie (also called a prefix tree) is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Implement the Trie class:

• void insert(String word)
• boolean search(String word) — returns true if word is in the trie.
• boolean startsWith(String prefix) — returns true if any word has this prefix.

Example:

insert("apple"), search("apple")→true, search("app")→false, startsWith("app")→true,
insert("app"), search("app")→true