# I'm studying a trie tree, where I want to delete a word, Please make me understand the algorithm

def delete(root: Node, key: str) -> bool:
"Eagerly delete the key from the trie rooted at root.
Return whether the trie rooted at root is now empty.
"""

def _delete(node: Node, key: str, d: int) -> bool:
"""Clear the node corresponding to key[d], and delete the child key[d+1]
if that subtrie is completely empty, and return whether node has been
cleared.
"""
if d == len(key):
node.value = None
else:
c = key[d]
if c in node.children and _delete(node.children[c], key, d+1):
del node.children[c]
# Return whether the subtrie rooted at node is now completely empty
return node.value is None and len(node.children) == 0

return _delete(root, key, 0)


I cannot able to understand what is the purpose of 'd' here anyone please explain me in detail?

• Have a look at the actual parameter in the two-parameter delete(), and at the tail-recursive one in _delete(). Note that while there are docstrings, you are left with above question: Write a better one, and/or find a better name for that parameter. Jun 21, 2021 at 14:00
• We're not a coding site, so I'm not sure that asking us to reverse-engineer how code works is going to be the best fit here.
– D.W.
Jun 21, 2021 at 22:07

d is the depth of the current node. In the Trie data structure, the first character is stored at the first level, and the second character is stored at the second level, etc. So, at depth d, we seek the node that matches the d-th character of the search string.

Exposed delete(root, key) method calls inner delete(node, key, d) method, with d=0 and node=root. That is very meaningful since we are processing the first character of key and we are at depth 0.

Assuming key is not empty, code will continue with the else branch. c=key[0]. That is the first character of key. node.children is a dictionary with keys of characters and values of Nodes. node.children[c] is node.children[key[0]] at the first round: Take the node that holds first character of key.

Now, we should proceed with recursion: increase depth by one, which is the same as the index of the next character of the key. Use the currently retrieved node from node.children[c] as the current node.

The process continues until we exhaust the search string: key. That is mentioned on the basis of the recursion.

The return value, although not asked in the question, means: The processed node is now empty - it does not store any key by itself and it does not have any children. This is used in the upper level of recursion, to decide if we should delete the processed node or not.

• Thank you so much! again, thank you so much! Jun 23, 2021 at 11:37