LeetCode #208 - Implement Trie (Prefix Tree)\nImplement a trie with insert, search, and startsWith methods. A trie (pronounced as 'try') is a special data structure used to store a dynamic set or associative array where the keys are usually strings. It is a tree-like data structure where each node represents a character of the string.\n\n**Example**:\n**Input**: \n"insert" - "apple" \n"search" - "apple" \n"search" - "app" \n"startsWith" - "app" \n"insert" - "app" \n"search" - "app" \n\n**Output**: \ntrue \nfalse \ntrue \ntrue \n\n**Constraints**: \n1. All inputs are lowercase letters a-z. \n2. The inputs are strings of at most 200 characters. \n3. The maximum number of inserts in the trie is 10000.

``` class TrieNode:\n def __init__(self):\n self.children = {}\n self.is_end_of_word = False\n\nclass Trie:\n def __init__(self):\n self.root = TrieNode()\n\n def insert(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n node.children[char] = TrieNode()\n node = node.children[char]\n node.is_end_of_word = True\n\n def search(self, word):\n node = self.root\n for char in word:\n if char not in node.children:\n return False\n node = node.children[char]\n return node.is_end_of_word\n\n def startsWith(self, prefix):\n node = self.root\n for char in prefix:\n if char not in node.children:\n return False\n node = node.children[char]\n return True ```