class TrieNode:

    #Constructor, Time O(1), Space O(1)
    def __init__(self, c):
        self.data = c
        self.children = [] # list     
        self.isEnd = False

    #find the node by char, the same functionality as children[ch] in array implementation 
	#Time O(k), Space O(1), k is number of children of this node    
    def getChild(self, c):
        if self.children != None:
            for child in self.children:
                if child.data == c:
                    return child
        return None
       
class Trie:
    #Constructor, Time O(1), Space O(1)
    def __init__(self):
        self.root = TrieNode('')

    #Add a word to trie, Iteration, Time O(s), Space O(s), 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 node.getChild(ch) == None:
                node.children.append(TrieNode(ch))
            node = node.getChild(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 node.getChild(ch) == None:
                return False
            node = node.getChild(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 (node.getChild(ch) == None) :
                return
            node = node.getChild(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:
            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 = "betty"
    print("find " + key + ": " + str(trie.search(key)))

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