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 search_perfix() functions.

Input

The input for all three of the functions mentioned above will be ...