We can use a while loop to determine the appropriate place to assign our word as a child key in a children hash. It does this by trying to look for each of our word's characters in the current node's children hash, and if there's a match, we try to place it in the next child's children hash. This handles the case where lineages like c -> a -> t in "category" may have already been previously added with a word like "cater".

1def add(self, key):
2    # add key into trie if not present
3    # else just marks the leaf node
4    pCrawl = self.root
5    length = len(key)
6    for level in range(length):
7        index = self._charToIndex(key[level])