Trie Deletion: Removing Words
What You'll Learn
You'll learn how to remove words from a Trie while keeping shared prefixes intact and cleaning up nodes that are no longer needed.
The Challenge of Deletion
Deleting a word from a Trie isn't as simple as removing its end marker. You need to carefully remove only the nodes that no longer serve any purpose, while preserving parts of the Trie that other words still use.
Think of it like pruning a tree: you want to cut dead branches, but only back to where they join a living branch.
The Three Scenarios
When deleting a word, you'll encounter one of three cases:
-
Word is a prefix of another word (e.g., deleting "car" when "card" exists): Just unmark the end-of-word flag at 'r'. Don't delete any nodes.
-
Word shares a prefix with other words (e.g., deleting "card" when "car" exists): Delete nodes from the unique suffix backward ('d'), but stop at the shared prefix.
-
Word is completely unique (e.g., deleting "zebra" when no other 'z' words exist): Delete all nodes from the end back to the root, or until you hit a node that's still being used.
The Deletion Algorithm
Start at the word's last character and work backward. At each node, ask: "Is this node still useful?" A node is useful if:
- It marks the end of another word, OR
- It has children (branches to other words)
If neither condition is true, delete it and continue backward. Stop when you find a node that's still needed.
Key Takeaway: Trie deletion requires careful backtracking to remove only unused nodes, preserving shared prefixes by checking if each node still serves a purpose (marking a word end or branching to other words).