There are two ways to do this, depending on whether you want to check whether you're removing the last path through any internal node (which makes removes slightly slower, but potentially makes searches after the removes slightly faster). Both ways are trivial to do recursively, but if you want to unroll it iteratively (as your insert
does), not checking is easier, so I'll do that.
def delete(self, word):
node = self
for letter in word[:-1]:
if letter not in node.children:
return False
node = node.children[letter]
if word[-1] in node.children:
del node.children[letter]
return True
return False
Can you make this faster? Yes, but it may not matter.
First, you know that the nodes will always exist, so you can remove some of the error checking. More importantly, if you can make the search function return the nodes, instead of just their values, that will make things a little faster. If you can add backlinks up the trie, that means you can erase the node in constant time instead of repeating the search. If you don't want backlinks up the trie, you can get the exact same benefit by returning a zipper instead of a node—or, more simply, just returning a stack of nodes.
But really, the worst case here is just doubling the work, not increasing the algorithmic complexity or multiplying by a large factor, so simple probably wins.