Deletion in Trie
Explore how to delete words in a trie by understanding different scenarios such as words with no suffix, words as prefixes, and words sharing common prefixes. Learn the step-by-step recursive approach to safely remove or unmark nodes in a trie structure using Python, along with insights into its time complexity.
Deleting a Word in a Trie
While deleting a node, we need to make sure that the node that we are trying to delete does not have any further child branches. If there are no branches, then we can easily remove the node.
However, if the node contains child branches, this opens up a few scenarios which we will cover below.
Case 1: Word with No Suffix or Prefix
If the word to be deleted has no suffix or prefix and all the character nodes of this word do not have any other children, then we will delete all these nodes up to the root.
However, if any of these nodes have other children (are part of another branch), then they will not be deleted. This will be explained further in Case 2.
In the figure below, the deletion of the word bat would mean that we have to delete all characters of bat.
Case 2: Word is a Prefix
If the word to be deleted is a prefix of some other word, then the value of is_end_word of the last node of that word is set to False and no node is deleted.
For example, to delete the word the, we will simply unmark e to show that the word doesn’t exist anymore.
Case 3: Word Has a Common Prefix
If the word to be deleted has a common prefix and the last node of that word does not have any children, then this node is deleted along with all the parent nodes in the branch which do not have any other children and are not end characters.
Take a look at the figure below. In order to delete their, we’ll traverse the common path up to the and delete the characters i and r.