class TrieNode:    

    #Constructor, Time O(1), Space O(1), 128 is constant
    def __init__(self, c):
        self.children = [None]*128 #don't use 26 if there is space or other special characters
        self.isEnd = False
        self.data = c

class Trie:

    #Constructor, Time O(1), Space O(1)
    def __init__(self):
        self.root = TrieNode('')

    #inserts a word into the 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:
            idx = ord(ch)
            if not node.children[idx]:
                node.children[idx] =  TrieNode(ch)
            node = node.children[idx]
        node.isEnd = True

    #Find word in trie, Iteration, Time O(s) Space O(1), s is word length
    def search(self, key):
        node = self.root
        for ch in key:
            index = ord(ch)
            if not node.children[index]:
                return False
            node = node.children[index] 
        return node.isEnd

    #Remove a word, Iteration, Time O(s), Space O(1)
    def delete(self, word) :
        if self.search(word) == False:
            print(word + " does not exist in trie.")
            return
        node = self.root
        for ch in word: 
            index = ord(ch)
            if not node.children[index]:
                return 
            node = node.children[index]            
        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 == None:
            return
        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 = "apple"
    print("find " + key + ": " + str(trie.search(key)))

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