class TrieNode:

    #constructor, Time O(1) Space O(1)
    def __init__(self, c):
        self.data = c
        self.isEnd = False
        self.children = {} #map

class Trie:
    #constructor, Time O(1) Space O(1)
    def __init__(self):
        self.root = TrieNode('')
    
    #Add a word to trie, Time O(s) Space O(1), s is word length
    def insert(self, word):
        if self.search(word) == True:
            print(word + " is already in trie.")
            return  
        node = self.root
        for ch in word:
            if not ch in node.children:
                node.children[ch] = TrieNode(ch)   
            node = node.children[ch]                 
        node.isEnd = True

    #Search a word in trie, Iteration, Time O(s), Space O(1), s is word length
    def search(self, word):
        node = self.root
        for ch in word:           
            if not ch in node.children:
                return False
            node = node.children.get(ch)
        return node.isEnd

    #Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length
    def delete(self, word) :
        if self.search(word) == False:
            print(word + " does not exist in trie.")
            return
        node = self.root
        for ch in word: 
            if not ch in node.children:
                return
            node = node.children.get(ch)    
        node.isEnd = False

    #Print all words in trie, call recursion function
	#Time O(n), Space O(n), n is number of nodes in trie
    def print (self) :
        res = []
        self.helper(self.root,res, "") 
        print(res)

	#recursion function, Time O(n), Space O(n), n is number of nodes in trie
    def helper(self, node, res, prefix):
        if node.isEnd:
            res.append(prefix + node.data)       
        for child in node.children.values():
            self.helper(child, res, prefix + node.data)

if __name__ == '__main__':
    trie = Trie()      
    trie.insert("ana") 
    trie.insert("anna")
    trie.insert("anne")          
    trie.insert("apple")
    trie.insert("betty")
    trie.print()

    key = "apple"
    print("find " + key + ": " + str(trie.search(key)))

    trie.delete(key)
    trie.print()
    print("find " + key + ": " + str(trie.search(key)))