Implement Trie (Prefix Tree)

A prefix tree (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems. Examples Example 1: Input: ["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"] Output: [null, null, true, false, true, null, true] Explanation: PrefixTree prefixTree = new PrefixTree(); prefixTree.insert("dog"); prefixTree.search("dog"); // return true prefixTree.search("do"); // return false prefixTree.startsWith("do"); // return true prefixTree.insert("do"); prefixTree.search("do"); // return true Constraints 1 <= word.length, prefix.length <= 1000 word and prefix are made up of lowercase English letters.