Deletion in a Trie
Explore the process of deleting words in a Trie data structure. This lesson helps you understand different scenarios such as words with no common prefix, prefix words, and common prefixes. Learn how to implement the deletion method efficiently in Java and grasp the underlying logic and time complexity involved.
Deleting a word in Trie #
While deleting a word from a Trie, we make sure that the node that we are trying to delete does not have any further branches. If there are no branches, then we can easily remove the node. However, if the node contains further branches then this opens up a lot of the scenarios covered below.
Case 1: If the word to be deleted has no common subsequence #
- If the word to be deleted has no common subsequence, then all the nodes of that word are deleted.
For example, in the figure given below, we have to delete all characters of “bat” in order to delete the word bat.
Case 2: If the word to be deleted is a prefix of some other word #
- If the word to be deleted is a prefix of some other word, then the value of
isEndWordof the last node of that word is set tofalse, and no node is deleted.
For ...