We can search the trie in O(n) time with n being the length of the word.
Finally, we can implement remove.
To know whether we should remove something, we should first check if the word is in the trie. So first, we'll need to do a search for it and see if we get a depth value returned.
1def remove(self, root, key, depth=0):
2 pCrawl = self.root
3
4 if not pCrawl:
5 return None
6
7 # if last character of key is being processed
8 if depth == len(key):
9 # this node is no more end of word after removal of given key
10 if pCrawl.isEndOfWord:
11 pCrawl.isEndOfWord = False
12 # If key given is not prefix of any other word
13 if self._empty(pCrawl):
14 pCrawl = None
15 return pCrawl