a trieprefix tree is a kind of search tree used to provide quick lookup of wordspatterns in a set of words a basic trie however has on2 space complexity making it impractical in practice it however provides omaxsearchstring length of longest word lookup time making it an optimal approach when space is not an issue inserts a list of words into the trie param words list of string words return none inserts a word into the trie param word word to be inserted return none tries to find word in a trie param word word to look for return returns true if word is found false otherwise deletes a word in a trie param word word to delete return none if word does not exist if char not in current trie node flag to check if node can be deleted prints all the words in a trie param node root node of trie param word word variable should be empty at start return none printwordsroot pytests mapping from char to trienode inserts a list of words into the trie param words list of string words return none inserts a word into the trie param word word to be inserted return none tries to find word in a trie param word word to look for return returns true if word is found false otherwise deletes a word in a trie param word word to delete return none if word does not exist if char not in current trie node flag to check if node can be deleted prints all the words in a trie param node root node of trie param word word variable should be empty at start return none print_words root pytests
class TrieNode:
    def __init__(self) -> None:
        self.nodes: dict[str, TrieNode] = {}  
        self.is_leaf = False

    def insert_many(self, words: list[str]) -> None:
        
        for word in words:
            self.insert(word)

    def insert(self, word: str) -> None:
        
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True

    def find(self, word: str) -> bool:
        
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

    def delete(self, word: str) -> None:
        

        def _delete(curr: TrieNode, word: str, index: int) -> bool:
            if index == len(word):
                
                if not curr.is_leaf:
                    return False
                curr.is_leaf = False
                return len(curr.nodes) == 0
            char = word[index]
            char_node = curr.nodes.get(char)
            
            if not char_node:
                return False
            
            delete_curr = _delete(char_node, word, index + 1)
            if delete_curr:
                del curr.nodes[char]
                return len(curr.nodes) == 0
            return delete_curr

        _delete(self, word, 0)


def print_words(node: TrieNode, word: str) -> None:
    
    if node.is_leaf:
        print(word, end=" ")

    for key, value in node.nodes.items():
        print_words(value, word + key)


def test_trie() -> bool:
    words = "banana bananas bandana band apple all beast".split()
    root = TrieNode()
    root.insert_many(words)
    
    assert all(root.find(word) for word in words)
    assert root.find("banana")
    assert not root.find("bandanas")
    assert not root.find("apps")
    assert root.find("apple")
    assert root.find("all")
    root.delete("all")
    assert not root.find("all")
    root.delete("banana")
    assert not root.find("banana")
    assert root.find("bananas")
    return True


def print_results(msg: str, passes: bool) -> None:
    print(str(msg), "works!" if passes else "doesn't work :(")


def pytests() -> None:
    assert test_trie()


def main() -> None:
    
    print_results("Testing trie functionality", test_trie())


if __name__ == "__main__":
    main()