Deletion in Trie
Explore how to delete words from a trie with a focus on different cases such as words with no suffix or prefix, words that are prefixes, and words with common prefixes. Understand the recursive deletion process and its time complexity, helping you implement trie deletion confidently for interview preparation.
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 ...