Tries

"""
A trie (pronounced "try") is a tree-like data structure that is used to efficiently store and search a dynamic set of strings. Tries are particularly useful for tasks involving prefix matching and fast retrieval of strings.
"""

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

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

    # Insert a word into the trie
    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

    # Search for a word in the trie
    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

    # Check if there is any word in the trie that starts with the given prefix
    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

    # Delete a word from the trie
    def delete(self, word):
        def _delete(node, word, depth):
            if not node:
                return False

            if depth == len(word):
                if not node.is_end_of_word:
                    return False
                node.is_end_of_word = False
                return len(node.children) == 0

            char = word[depth]
            if char not in node.children:
                return False

            should_delete_current_node = _delete(node.children[char], word, depth + 1)

            if should_delete_current_node:
                del node.children[char]
                return len(node.children) == 0

            return False

        _delete(self.root, word, 0)

    # Get all words stored in the trie
    def get_all_words(self):
        def _get_all_words(node, prefix, words):
            if node.is_end_of_word:
                words.append(prefix)

            for char, next_node in node.children.items():
                _get_all_words(next_node, prefix + char, words)

        words = []
        _get_all_words(self.root, "", words)
        return words

# Example usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("apricot")
trie.insert("banana")