Trie (Prefix Tree)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def delete(self, word):
        def erase(node, i):
            if i == len(word):
                if not node.is_end_of_word:
                    return False, False
                node.is_end_of_word = False
                return True, not node.children
            child = node.children.get(word[i])
            if child is None:
                return False, False
            deleted, prune = erase(child, i + 1)
            if prune:
                del node.children[word[i]]
            return deleted, (not node.is_end_of_word and not node.children)

        deleted, _ = erase(self.root, 0)
        return deleted

trie = Trie()
for value in ("app", "apple", "café"): trie.insert(value)
assert trie.search("app") and trie.starts_with("ap")
assert trie.delete("app") and not trie.search("app") and trie.search("apple")

import java.util.HashMap;
import java.util.Map;
import java.util.PrimitiveIterator;

class Trie {
    private static final class Node {
        final Map<Integer, Node> children = new HashMap<>();
        boolean terminal;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        PrimitiveIterator.OfInt points = word.codePoints().iterator();
        while (points.hasNext()) {
            int codePoint = points.nextInt();
            node = node.children.computeIfAbsent(codePoint, ignored -> new Node());
        }
        node.terminal = true;
    }

    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.terminal;
    }

    public boolean startsWith(String prefix) { return find(prefix) != null; }

    public boolean delete(String word) {
        if (!search(word)) return false;
        erase(root, word.codePoints().toArray(), 0);
        return true;
    }

    private boolean erase(Node node, int[] word, int index) {
        if (index == word.length) node.terminal = false;
        else {
            Node child = node.children.get(word[index]);
            if (erase(child, word, index + 1)) node.children.remove(word[index]);
        }
        return !node.terminal && node.children.isEmpty();
    }

    private Node find(String text) {
        Node node = root;
        PrimitiveIterator.OfInt points = text.codePoints().iterator();
        while (points.hasNext()) {
            int codePoint = points.nextInt();
            node = node.children.get(codePoint);
            if (node == null) return null;
        }
        return node;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app"); trie.insert("apple"); trie.insert("café");
        if (!trie.search("app") || !trie.startsWith("ap")) throw new AssertionError();
        if (!trie.delete("app") || trie.search("app") || !trie.search("apple")) throw new AssertionError();
    }
}