Understanding Prefix Trees (Trie) with a Complete Java Implementation

A prefix tree, also known as a Trie, stores all possible prefixes of a set of words as keys in a hash‑like structure, allowing fast prefix queries. Each node can have up to 26 children, one for each lowercase English letter.

Using the example words apple, app, api, banana and bus, the article shows how the prefixes a, ap, app, appl, apple (and similarly for the b words) become keys, each mapping to the list of words that share that prefix.

When searching for the prefix ap, the Trie first follows the root's a child, then the p child, confirming that words starting with ap exist. For an exact query like bus, the traversal continues through b → u → s and checks the node’s end‑of‑word flag to verify a complete match.

Inserting a new word such as buy follows the same path: the algorithm creates missing nodes (e.g., the y child) and marks the final node as an end of word.

The article also provides a full Java implementation of a Trie, including the TrieNode class with an array of 26 children, methods for insert, search, startsWith, and a recursive delete operation, as well as a Trie wrapper class and a main method demonstrating usage.

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;
    public TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
    public void insert(String word) {
        TrieNode current = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }
    public boolean delete(String word) {
        return delete(this, word, 0);
    }
    private boolean delete(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord) return false;
            current.isEndOfWord = false;
            return canDelete(current);
        }
        char ch = word.charAt(index);
        int childIndex = ch - 'a';
        TrieNode child = current.children[childIndex];
        if (child == null) return false;
        boolean canDeleteChild = delete(child, word, index + 1);
        if (canDeleteChild) {
            current.children[childIndex] = null;
            return canDelete(current);
        }
        return false;
    }
    private boolean canDelete(TrieNode node) {
        if (node.isEndOfWord) return false;
        for (TrieNode child : node.children) {
            if (child != null) return false;
        }
        return true;
    }
    public boolean search(String word) {
        TrieNode current = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) return false;
            current = current.children[index];
        }
        return current.isEndOfWord;
    }
    public boolean startsWith(String prefix) {
        TrieNode current = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) return false;
            current = current.children[index];
        }
        return true;
    }
}

public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) { root.insert(word); }
    public boolean delete(String word) { return root.delete(word); }
    public boolean search(String word) { return root.search(word); }
    public boolean startsWith(String prefix) { return root.startsWith(prefix); }
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("app"));     // false
        System.out.println(trie.startsWith("app")); // true
        trie.insert("app");
        System.out.println(trie.search("app"));    // true
        trie.delete("apple");
        System.out.println(trie.search("apple"));  // false
    }
}