Finally, let's try to delete from a Trie:

1. Verify whether the given word is part of the Trie.
2. If it is part of the Trie, then simply remove it.

Deletion takes place in a bottom-up manner using recursion and following these rules:

• If the given word is not in the Trie, then nothing happens (return false)
• If the given word is unique (not part of another word), then delete all corresponding nodes (return true)
• If the given word is a prefix of another long word in the Trie, then set the leaf node flag to false (return false)
• If the given word has at least another word as a prefix, then delete the corresponding nodes from the end of the given word until the first leaf node of the longest prefix word (return false)

In terms of code lines, we have the following:

public boolean delete(String word) {
  return delete(root, word, 0);
}

private boolean delete(Node node, String word, int position) {

  if (word.length() == position) {
    if (!node.isWord()) {
      return false;
    }

    node.setWord(false);

    return node.getChildren().isEmpty();
  }

  char ch = word.charAt(position);
  Node children = node.getChildren().get(ch);

  if (children == null) {
    return false;
  }

  boolean deleteChildren = delete(children, word, position + 1);

  if (deleteChildren && !children.isWord()) {
    node.getChildren().remove(ch);

    return node.getChildren().isEmpty();
  }

  return false;
}

Now, we can build a Trie as follows:

Trie trie = new Trie();
trie.insert/contains/delete(...);