Implement a trie (prefix tree)

Implement a prefix tree over strings: insert a word, check whether a whole word is present, and check whether any stored word starts with a given prefix. Design the classes so that new operations can be added later without rewriting the structure, and explain the time and space cost of each operation.