from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isEnd = False
    def insert(self, word):
        node = self
        for w in word:
            node = node.children[w]
        node.isEnd = True
    def search(self, word):
        node = self
        for w in word:
            if w in node.children:
                node = node.children[w]
            else:
                return []
        # prefix match
        # traverse currnt node to all leaf nodes
        result = []
        self.traverse(node, list(word), result)
        return [''.join(r) for r in result]

    def traverse(self, root, prefix, result):
        if root.isEnd:
            result.append(prefix[:])
        for c,n in root.children.items():
            prefix.append(c)
            self.traverse(n, prefix, result)
            prefix.pop(-1)
if __name__ == "__main__":
    words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats']
    root = TrieNode()
    for w in words:
        root.insert(w)

    print (root.search('an')) # ['angle', 'angel']
    print (root.search('ap')) # ['apple']

for word in words:
        # create a temporary dict based off our root
        # dict object
        temp_dict = trie

        for letter in word:
            # update our temporary dict and add our current
            # letter and a sub-dictionary
            temp_dict = temp_dict.setdefault(letter, {})

        # If our word is finished, add {'*': '*'}
        # this tells us our word is finished
        temp_dict[_end] = _end
    return trie
def find_word(trie, word):
    sub_trie = trie
    mylist = []
    for letter in word:
        if letter in sub_trie:
            sub_trie = sub_trie[letter]
            mylist.append(letter)

        else:
            return False
    else:
        if _end in sub_trie:
            return True
        else:
            return False

# Test our trie creation
trie = make_trie('a', 'apple', 'angle', 'angel', 'bat', 'bats')
# print out our new trie
print(trie)
find = find_word(trie,"apple")
print (find)