Build a Basic Trie (Prefix Tree) for Autocomplete Features

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: str) -> None:
        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_prefix(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True # Prefix found (could be a full word or just a prefix)

    def _find_words_from_node(self, node: TrieNode, current_word: str, results: list):
        if node.is_end_of_word:
            results.append(current_word)
        for char, child_node in node.children.items():
            self._find_words_from_node(child_node, current_word + char, results)

    def autocomplete(self, prefix: str) -> List[str]:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return [] # No words start with this prefix
            node = node.children[char]
        
        results = []
        self._find_words_from_node(node, prefix, results)
        return results

# Example Usage:
trie = Trie()
trie.insert("apple")
trie.insert("apricot")
trie.insert("banana")
trie.insert("band")
trie.insert("application")

print(f"Does 'app' exist as prefix? {trie.search_prefix('app')}") # Output: True
print(f"Autocomplete for 'ap': {trie.autocomplete('ap')}") # Output: ['apple', 'apricot', 'application']
print(f"Autocomplete for 'ban': {trie.autocomplete('ban')}") # Output: ['banana', 'band']
print(f"Autocomplete for 'xyz': {trie.autocomplete('xyz')}") # Output: []