Interview Course Based on Story Questions

# Problem statement
In this challenge, you have to implement the **[Trie](https://www.educative.io/edpresso/what-is-a-prefix-tree)** 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 a string. The following is an example input:

```python3
"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 `search_prefix()` will return `true` if the input was found in the trie. Otherwise, it will return `false`. The following is an example output:
```python3
True
```



# Coding exercise
Using the skeleton code given below, you need to implement the `Trie` class with the `__init__()`, `insert(string)`, `search(string)`, and `search_prefix(string)` functions: 

DIY: Implement Trie

Problem statement