Java trie deletion: preserve shared prefixes and prune dead branches

Last updated: 29 Sept 20264 min read

tutorial

Trie deletion clears a word’s terminal marker and removes only branches that contain no remaining word or descendant.

Download Java source kit

Java 8+. The program uses JDK classes and requires no preview flags.

A prefix is shared storage

A command index stores pack and parcel. Deleting pack must not remove the shared pa path needed by parcel. A stored word can also be a prefix of another word, so clearing its terminal marker is separate from deleting the node itself.

The program records the path as it walks toward the word, then prunes backward after clearing the terminal marker. That avoids recursion proportional to an arbitrarily long input. The alphabet is deliberately restricted to lowercase ASCII, with a 4096-unit input budget.

Validation happens before mutation. An invalid final character must not cause the earlier valid prefix to disappear or create partial branches. A missing path or an unmarked prefix returns false without changing another word’s membership.

Do not invent ranking semantics

This structure answers exact membership and deletion. It does not rank suggestions, define language collation or compress long single-child paths. Those features need their own stored counts or ordering rules. Node pruning is a storage operation, not a popularity score update.

Working program

public class DeletableCommandTrie {
    static class Node {Node[] children=new Node[26];boolean terminal;}
    final Node root=new Node();
    static void validate(String word){
        if(word==null||word.isEmpty()||word.length()>4096)throw new IllegalArgumentException("Word budget");
        for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("Alphabet");
    }
    void add(String word){validate(word);Node n=root;for(int i=0;i<word.length();i++){int slot=word.charAt(i)-'a';if(n.children[slot]==null)n.children[slot]=new Node();n=n.children[slot];}n.terminal=true;}
    boolean contains(String word){validate(word);Node n=root;for(int i=0;i<word.length();i++){n=n.children[word.charAt(i)-'a'];if(n==null)return false;}return n.terminal;}
    static boolean empty(Node n){if(n.terminal)return false;for(Node child:n.children)if(child!=null)return false;return true;}
    boolean remove(String word){
        validate(word);Node[] path=new Node[word.length()+1];path[0]=root;
        for(int i=0;i<word.length();i++){path[i+1]=path[i].children[word.charAt(i)-'a'];if(path[i+1]==null)return false;}
        if(!path[word.length()].terminal)return false;path[word.length()].terminal=false;
        for(int i=word.length();i>0&&empty(path[i]);i--)path[i-1].children[word.charAt(i-1)-'a']=null;
        return true;
    }
    public static void main(String[] args){
        DeletableCommandTrie commands=new DeletableCommandTrie();commands.add("pack");commands.add("packing");commands.add("parcel");
        System.out.println(commands.remove("pack"));System.out.println(commands.contains("packing"));
        System.out.println(commands.remove("pack"));System.out.println(commands.remove("parcel"));
    }
}

Output

true
true
false
true

Costs and boundaries

For a word of length m, validation, traversal and pruning are O(m) with a fixed 26-slot alphabet. The recorded path uses O(m) temporary references. Live nodes retain 26 child positions each, so this representation can be wasteful for sparse or much larger alphabets.

Common Mistakes

Clearing a terminal marker is not permission to remove live descendants.
Validate the complete word before mutation.
A fixed ASCII trie is not a Unicode search index.