class Tree:
    def __init__(self):
        self.children = [None] * 26
        self.end = False

    def free(self):
        for c in self.children:
            if c:
                return False
        return True


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

    def _get_tree(self):
        return Tree()

    def _get_char_idx(self, char):
        return ord('a') - ord(char)

    def add(self, key):
        tree = self.root
        for c in key:
            char_idx = self._get_char_idx(c)

            if not tree.children[char_idx]:
                tree.children[char_idx] = self._get_tree()

            tree = tree.children[char_idx]

        tree.end = True


    def search(self, key):
        tree = self.root
        for c in key:
            char_idx = self._get_char_idx(c)
            if not tree.children[char_idx]:
                return False

            tree = tree.children[char_idx]

        return tree and tree.end


    def _delete(self, node, key, pos, key_len):
        if not node:
            return False

        if pos == key_len:
            if node.end:
                node.end = False
            return node.free()

        char_idx = self._get_char_idx(key[pos])
        if self._delete(
            node.children[char_idx], key, pos+1, key_len):

            del node.children[char_idx]

            return not node.end and node.free()

        return False

    def delete_key(self, key):
        key_len = len(key)
        if key_len > 0:
            return self._delete(self.root, key, 0, key_len)
        return False


  # Input keys (use only 'a' through 'z' and lower case)
keys = ["the","a","there","anaswe","any",
        "by","their"]
output = ["Not present in trie",
            "Present in trie"]

# Trie object
t = Trie()
# Construct trie
for key in keys:
    t.add(key)

# Search for different keys
print("{} ---- {}".format("the",output[t.search("the")]))
print("{} ---- {}".format("these",output[t.search("these")]))
print("{} ---- {}".format("their",output[t.search("their")]))
print("{} ---- {}".format("thaw",output[t.search("thaw")]))


key = "the"
print("{} ---- {}".format(key, output[t.search(key)]))
print("{} ---- {}".format(key, output[t.search(key)]))
print("{} ---- {}".format("their", output[t.search("their")]))