Implement Trie (Prefix Tree)

A trie, or prefix tree, is a tree that stores a set of strings. Each edge of the tree holds one letter. Words that start with the same letters share the same path from the root, the first node of the tree.

A prefix of a string is a part at the start of the string. For example, ca is a prefix of cart.

Write the class Trie with these operations:

Trie() creates an empty trie. insert(word) adds the string word to the trie. search(word) returns true if the trie has the string word, and false if it does not. startsWith(prefix) returns true if a string in the trie starts with prefix, and false if no string does.