Trie Deletion

Deletion is trickier than insertion. You can't remove nodes. Other words might share the path.

Simple approach: set isEndOfWord = false:

function delete(word):
    node = findNode(word)
    if node:
        node.isEndOfWord = false

This wastes space but is simple. The "deleted" word won't be found by search, but the nodes remain.

Full deletion requires checking if nodes are safe to remove:

function delete(word):
 function deleteHelper(node, word, depth):
 if depth == word.length:
 node.isEndOfWord = false
 return node.children.size == 0
 char = word[depth]
 if deleteHelper(node.children[char], word, depth + 1):
 remove node.children[char]
 return node.children.size == 0 and node.isEndOfWord == false
 return false
 deleteHelper(root, word, 0)

Remove nodes bottom-up only if they have no children and aren't word endings.