Implement Trie (Prefix Tree)

A trie, or prefix tree, organizes strings by their successive characters so that complete words and shared prefixes can be found efficiently. It is commonly useful for features such as autocomplete and spelling assistance. Create the PrefixTree class with these operations: PrefixTree() Creates an empty prefix tree. void insert(String word) Adds word to the tree. boolean search(String word) Reports true when word was previously inserted as a complete string; otherwise, it…