class Trie:

    def __init__(self):
        self.leaf_word = None
        self.children = {}
        """
        Initialize your data structure here.
        """


    def insert(self, word: str) -> None:
        curr_node = self
        for char in word:
            if char not in curr_node.children:
                curr_node.children[char] = Trie()
            curr_node = curr_node.children[char]
        curr_node.leaf_word = word


    def search(self, word: str) -> bool:
        curr_node = self
        for char in word:
            if char not in curr_node.children:
                return False
            curr_node = curr_node.children[char]
        return curr_node.leaf_word == word


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curr_node = self
        for char in prefix:
            if char not in curr_node.children:
                return False
            curr_node = curr_node.children[char]
        return True