DIY: Implement Trie

Problem statement

In this challenge, you have to implement the Trie data structure. This is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix matching operation. Your implementation of the trie should contain Insert(), Search(), and SearchPerfix() functions.

Input

The input for all three of the functions mentioned above will be a string. The following is an example input:

"makeup"

You can assume that all inputs will be lowercase character strings with string length less than 100.

Output

The Insert() function does not return anything. The Search() and SearchPrefix() will return true if the input was found in the trie. Otherwise, it will return false. The following is an example output:

true

Coding exercise

Using the skeleton code given below, you need to implement the Trie data structure with the newTrie(), Insert(string), Search(string), and SearchPrefix(string) functions: