Building a Trie for Efficient Prefix Searching

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def _collect_all_words(self, node, prefix, words):
        if node.is_end_of_word:
            words.append(prefix)
        for char, child_node in node.children.items():
            self._collect_all_words(child_node, prefix + char, words)

    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return [] # No words start with this prefix
            node = node.children[char]
        
        words = []
        self._collect_all_words(node, prefix, words)
        return words

# Example Usage:
# trie = Trie()
# trie.insert("apple")
# trie.insert("app")
# trie.insert("apricot")
# trie.insert("banana")
# trie.insert("bat")

# print(f"Search 'apple': {trie.search('apple')}") # True
# print(f"Search 'app': {trie.search('app')}")     # True
# print(f"Search 'appl': {trie.search('appl')}")   # False
# print(f"Starts with 'app': {trie.starts_with('app')}") # True
# print(f"Autocomplete 'ap': {trie.autocomplete('ap')}") # ['apple', 'app', 'apricot']
# print(f"Autocomplete 'b': {trie.autocomplete('b')}")   # ['banana', 'bat']