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
    }
}