0
$\begingroup$
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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Jun 21, 2021 at 14:00
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 21, 2021 at 22:07

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you so much! again, thank you so much! $\endgroup$
    – Adil Nehal
    Jun 23, 2021 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.