Deletion in a Trie

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 isEndWord of the last node of that word is set to false, and no node is deleted.

For example, we will simply unmark e to delete the word the and show that it doesn’t exist anymore.

Case 3: If the word to be deleted has a common prefix

• If the word to be deleted has a common prefix and the last node of that word is also the leaf node (i.e. the last node of its