Implement a Trie with Deletion

To implement a Trie with deletion, I first define a Node class containing a map of children and a boolean flag indicating if a word ends here. The core challenge lies in the delete function, which requires careful backtracking. My approach uses recursion. First, I check if the current node exists; if not, the key isn't there. If we reach the end of the key, I verify the end-of-word flag. If false, the key doesn't exist. If true, I set the flag to false. The crucial step happens during the return phase. After recursively calling delete on the child node, I check if that child node is now empty. A node is considered empty if it has no children AND its end-of-word flag is false. If both conditions are met, I remove the child reference from the parent. This ensures we don't orphan nodes needed for other words like 'app' when deleting 'apple'. For example, deleting 'car' from a trie containing 'cart' and 'card' would require checking children after removal. Since 'c' and 'a' share prefixes with other words, they remain. Only the specific path for 'r' might be pruned if it becomes isolated. This method guarantees O(L) time complexity, where L is the string length, and maintains the Trie's efficiency for lookups and insertions.