For http://stackoverflow.com/questions/15709261/how-to-implement-the-remove-function-of-a-trie-in-python

trie.py

class Trie():
    def __init__(self, words=()):
        self.root = {}
        for word in words:
            self.add(word)

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current["end"] = "end"

    def remove(self, word):
        current = self.root
        last_full = current
        last_full_letter = word[0]

        for letter in word:
            if letter not in current:
                raise ValueError("Word not in Trie")
            if len(current) > 1:
                last_full = current
                last_full_letter = letter
            current = current[letter]
            
        if "end" not in current:
            raise ValueError("Word not in Trie")
        if len(current) > 1:
            del current[end]
        else:
            del last_full[last_full_letter]

    def __contains__(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]
        return "end" in current

    def _lexical_traversal(self, current, prefix):
        order = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz"
        if "end" in current:
            yield "".join(prefix)

        for letter in order:
            try:
                next = current[letter]
                yield from self._lexical_traversal(next, prefix+[letter])
            except KeyError:
                pass

    def get_prefix(self, prefix):
        current = self.root
        for letter in prefix:
            if letter not in current:
                return ()
            current = current[letter]
        return self._lexical_traversal(current, list(prefix))

    def __iter__(self):
        yield from self._lexical_traversal(self.root, [])

    def __repr__(self):
        return "{}({})".format(self.__class__.__name__, list(self))