Java trie: prefix lookup with a declared alphabet

Last updated: 29 Sept 20264 min read

tutorial

A trie stores a path for each key prefix so exact membership and prefix membership can be tested separately.

Java 8+. This is a complete program using JDK classes.

Validate before creating a path

A parcel command dictionary accepts lowercase ASCII words. Each node has 26 child positions. That fixed alphabet keeps this implementation small; it is not a Unicode word dictionary.

The entire input is checked before insertion. If an invalid character were discovered halfway through creating nodes, a rejected command could leave partial paths that make later prefix checks succeed. The validation boundary prevents that particular mutation leak.

A terminal flag distinguishes a complete command from a prefix. Inserting parcel makes par a reachable path, but does not make par a stored command. An empty prefix is accepted as a query for the dictionary root; an empty command is rejected.

Working program

public class ParcelCommandTrie {
    static final class Node { final Node[] children = new Node[26]; boolean terminal; }
    final Node root = new Node();
    static void validate(String text, boolean allowEmpty) {
        if (text == null || (!allowEmpty && text.isEmpty())) throw new IllegalArgumentException("Missing word");
        for (int i=0; i<text.length(); i++)
            if (text.charAt(i) < 'a' || text.charAt(i) > 'z') throw new IllegalArgumentException("ASCII lowercase required");
    }
    void add(String word) {
        validate(word, false); Node current = root;
        for (int i=0; i<word.length(); i++) {
            int slot = word.charAt(i)-'a';
            if (current.children[slot] == null) current.children[slot] = new Node();
            current = current.children[slot];
        }
        current.terminal = true;
    }
    Node find(String text) {
        validate(text, true); Node current = root;
        for (int i=0; i<text.length(); i++) {
            current = current.children[text.charAt(i)-'a'];
            if (current == null) return null;
        }
        return current;
    }
    boolean contains(String word) { Node n=find(word); return n != null && n.terminal; }
    boolean hasPrefix(String prefix) { return find(prefix) != null; }
    public static void main(String[] args) {
        ParcelCommandTrie commands = new ParcelCommandTrie();
        commands.add("parcel"); commands.add("packing"); commands.add("label");
        System.out.println(commands.hasPrefix("pack"));
        System.out.println(commands.contains("pack"));
        System.out.println(commands.contains("parcel"));
        try { commands.add("Parcel"); }
        catch (IllegalArgumentException rejected) { System.out.println("Alphabet rejected"); }
    }
}

Output

true
false
true
Alphabet rejected

Costs and boundaries

Insertion and queries inspect O(L) characters for a key of length L. New storage is proportional to previously absent prefix nodes, each carrying 26 reference slots. A sparse child map trades that array cost for lookup and allocation costs. This model does not implement deletion or ranking of suggestions.

Common Mistakes

A reachable prefix is not necessarily a stored word.
Validate the full alphabet before mutating.
Do not use a 26-slot trie for arbitrary Unicode code points.

Continue the contract

Deletion must preserve terminal markers and shared prefixes belonging to surviving words. The deletion companion uses a bounded iterative path and checks rejection before mutation.

Open the companion lesson.

java

trie