trie delete pseudocode
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)